Processing high data rate streams in System S.

Proceedings of the 2010 Conference on Intelligent Data Understanding

Agents and Data Mining Interaction
is described. The central feature of the framework is that it avoids the use of ontologies or agreed meta-language formats by supporting a system of wrappers. The advantage offered is that the system is easily extendable, further data agents and mining agents can simply be added to the system. A demonstration EMADS framework is currently available. The paper includes details of the EMADS architecture and the wrapper principle incorporated into it. A full description of the framework’s operation is provided by considering two AEDM scenarios; the scenarios are also the focus for an evaluation of the framework. 1.
On wavelet decomposition of uncertain time series data sets.

Orientation distance%2Dbased discriminative feature extraction for multi%2Dclass classification.

Detecting Leaders from Correlated Time Series.

Mining Diversity on Networks.

Pocket Data Mining Towards Collaborative Data Mining in Mobile Computing Environments.

UP%2DGrowth an efficient algorithm for high utility itemset mining.

k%2DSupport anonymity based on pseudo taxonomy for outsourcing of frequent itemset mining.

Semi%2Dsupervised feature selection for graph classification.

Detecting abnormal coupled sequences and sequence changes in group%2Dbased manipulative trading behaviors.

BASSET Scalable Gateway Finder in Large Graphs.

Online mining of temporal maximal utility itemsets from data streams.

On Clustering Graph Streams.

On Clustering Graph Streams.



Predictive Modeling with Heterogeneous Sources.

Mining knowledge from databases an information network analysis approach.

Mining Concept%2DDrifting Data Streams.
Recently, mining data streams with concept drifts for actionable insights has become an important and challenging task for a wide range of applications including credit card fraud protection, target marketing, network intrusion detection, etc. Conventional knowledge discovery tools are facing two challenges, the overwhelming volume of the streaming data, and the concept drifts. In this paper, we propose a general framework for mining concept-drifting data streams using weighted ensemble classifiers. We train an ensemble of classification models, such as C4.5, RIPPER, naive Bayesian, etc., from sequential chunks of the data stream. The classifiers in the ensemble are judiciously weighted based on their expected classification accuracy on the test data under the time-evolving environment. Thus, the ensemble approach improves both the efficiency in learning the model and the accuracy in performing classification. Our empirical study shows that the proposed methods have substantial advantage over single-classifier approaches in prediction accuracy, and the ensemble framework is effective for a variety of classification models.
Privacy%2Dpreserving data publishing A survey of recent developments.
The collection of digital information by governments, corporations, and individuals has created tremendous opportunities for knowledge- and information-based decision making. Driven by mutual benefits, or by regulations that require certain data to be published, there is a demand for the exchange and publication of data among various parties. Data in its original form, however, typically contains sensitive information about individuals, and publishing such data will violate individual privacy. The current practice in data publishing relies mainly on policies and guidelines as to what types of data can be published, and agreements on the use of published data. This approach alone may lead to excessive data distortion or insufficient protection. Privacy-preserving data publishing (PPDP) provides methods and tools for publishing useful information while preserving data privacy. Recently, PPDP has received considerable attention in research communities, and many approaches have been proposed for different data publishing scenarios. In this survey, we will systematically summarize and evaluate different approaches to PPDP, study the challenges in practical data publishing, clarify the differences and requirements that distinguish PPDP from other related problems, and propose future research directions.
Music Recommendation Using Content and Context Information Mining.

Guest Editors%27 Introduction Social Computing in the Blogosphere.

Introduction to the Domain%2DDriven Data Mining Special Section.

On clustering massive text and categorical data streams.
Many applications such as news group filtering, text crawling, and document organization require real time clustering and segmentation of text data records. The categorical data stream clustering problem also has a number of applications to the problems of customer segmentation and real time trend analysis. We will present an online approach for clustering massive text and categorical data streams with the use of a statistical summarization methodology. We present results illustrating the effectiveness of the technique.
A general framework for relation graph clustering.

A general framework for relation graph clustering.

On Dense Pattern Mining in Graph Streams.
Many massive web and communication networkapplications create data which can be represented as a massive sequential stream of edges. For example, conversations in a telecommunication network or messages in a social network can be represented as a massive stream of edges. Such streams are typically very large, because of the large amount of underlying activity in such networks. An important application in these domains is to determine frequently occurring dense structures in the underlying graph stream. In general, we would like to determine frequent and dense patterns in the underlying interactions. We introduce a model for dense pattern mining and propose probabilistic algorithms for determining such structural patterns effectively and efficiently. The purpose of the probabilistic approach is to create a summarization of the graph stream, which can be used for further pattern mining. We show that this summarization approach leads to effective and efficient results for stream pattern mining over a number of real and synthetic data sets. 1.
Personalized Privacy Protection in Social Networks.

Discriminative frequent subgraph mining with optimality guarantees.

A framework for clustering massive graph streams.

Optimal distance bounds for fast search on compressed time%2Dseries query logs.

Rights protection of trajectory datasets with nearest%2Dneighbor preservation.

ICDM 2009
Abstract—With the assistance of a domain expert, active learning can often select or construct fewer examples to request their labels to build an accurate classifier. However, previous works of active learning can only generate and ask specific queries. In real-world applications, the domain experts (or oracles) are often more readily to answer “generalized queries ” with don’t-care attributes. The power of such generalized queries is that one generalized query is often equivalent to many specific ones. However, overly general queries are not good as answers from the domain experts (or oracles) can be highly uncertain, and this makes learning difficult. In this paper, we propose a novel active learning algorithm that asks good generalized queries. We then extend our algorithm to construct new, hierarchical features for both nominal and numeric attributes. We demonstrate experimentally that, our new method asks significantly fewer queries compared with the previous works of active learning, even when the initial labeled dataset is very small, and the oracle is inaccurate in class probability estimations. Our method can be readily deployed in real-world data mining tasks where obtaining labeled examples is costly. This is an extension of the paper published in IEEE ICDM 2009 [16]. Keywords—active learning, domain expert, generalized query. 1
ICDM 2009
Abstract—With the assistance of a domain expert, active learning can often select or construct fewer examples to request their labels to build an accurate classifier. However, previous works of active learning can only generate and ask specific queries. In real-world applications, the domain experts (or oracles) are often more readily to answer “generalized queries ” with don’t-care attributes. The power of such generalized queries is that one generalized query is often equivalent to many specific ones. However, overly general queries are not good as answers from the domain experts (or oracles) can be highly uncertain, and this makes learning difficult. In this paper, we propose a novel active learning algorithm that asks good generalized queries. We then extend our algorithm to construct new, hierarchical features for both nominal and numeric attributes. We demonstrate experimentally that, our new method asks significantly fewer queries compared with the previous works of active learning, even when the initial labeled dataset is very small, and the oracle is inaccurate in class probability estimations. Our method can be readily deployed in real-world data mining tasks where obtaining labeled examples is costly. This is an extension of the paper published in IEEE ICDM 2009 [16]. Keywords—active learning, domain expert, generalized query. 1
Agents and Data Mining Interaction
is described. The central feature of the framework is that it avoids the use of ontologies or agreed meta-language formats by supporting a system of wrappers. The advantage offered is that the system is easily extendable, further data agents and mining agents can simply be added to the system. A demonstration EMADS framework is currently available. The paper includes details of the EMADS architecture and the wrapper principle incorporated into it. A full description of the framework’s operation is provided by considering two AEDM scenarios; the scenarios are also the focus for an evaluation of the framework. 1.
Online Auctions There Can Be Only One.

Scalable OLAP and mining of information networks.

PROUD a probabilistic approach to processing similarity queries over uncertain data streams.

Distributed Processing of Spatial Alarms A Safe Region%2DBased Approach.
Spatial alarms are considered as one of the basic capabilities in future mobile computing systems for enabling personalization of location-based services. In this paper, we propose a distributed architecture and a suite of safe region techniques for scalable processing of spatial alarms. We show that safe region-based processing enables resource optimal distribution of partial alarm processing tasks from the server to the mobile clients. We propose three different safe region computation algorithms to explore the impact of size and shape of the safe region on network bandwidth, server load and client energy consumption. Concretely, we show that the maximum weighted perimeter rectangular safe region approach outperforms previous techniques in terms of performance and accuracy. We further explore finer granularity safe regions by introducing grid-based and pyramidbased representation of rectilinear polygonal shapes using bitmap encoding. Our experimental evaluation shows that the distributed safe region-based architecture outperforms the two most popular server-centric approaches, periodic and safe period-based, for spatial alarm processing. 1.
Privacy%2DPreserving Singular Value Decomposition.

Scale%2DUp Strategies for Processing High%2DRate Data Streams in System S.

On Efficient Query Processing of Stream Counts on the Cell Processor.



Why Naive Ensembles Do Not Work in Cloud Computing.

Efficient Incremental Mining of Qualified Web Traversal Patterns without Scanning Original Databases.

Early Prediction on Time Series A Nearest Neighbor Approach.
In this paper, we formulate the problem of early classification of time series data, which is important in some time-sensitive applications such as healthinformatics. We introduce a novel concept of MPL (Minimum Prediction Length) and develop ECTS (Early Classification on Time Series), an effective 1-nearest neighbor classification method. ECTS makes early predictions and at the same time retains the accuracy comparable to that of a 1NN classifier using the full-length time series. Our empirical study using benchmark time series data sets shows that ECTS works well on the real data sets where 1NN classification is effective. 1
Near%2Doptimal Supervised Feature Selection among Frequent Subgraphs.
Graph classification is an increasingly important step in numerous application domains, such as function prediction of molecules and proteins, computerised scene analysis, and anomaly detection in program flows. Among the various approaches proposed in the literature, graph classification based on frequent subgraphs is a popular branch: Graphs are represented as (usually binary) vectors, with components indicating whether a graph contains a particular subgraph that is frequent across the dataset. On large graphs, however, one faces the enormous problem that the number of these frequent subgraphs may grow exponentially with the size of the graphs, but only few of them possess enough discriminative power to make them
Optimal Distance Bounds on Time%2DSeries Data.
Most data mining operations include an integral search component at their core. For example, the performance of similarity search or classification based on Nearest Neighbors is largely dependent on the underlying compression and distance estimation techniques. As data repositories grow larger, there is an explicit need not only for storing the data in a compressed form, but also for facilitating mining operations directly on the compressed data. Naturally, the quality or tightness of the estimated distances on the compressed objects directly affects the search performance. We motivate our work within the setting of search engine weblog repositories, where keyword demand trends over time are represented and stored as compressed timeseries data. Search and analysis over such sequence data has important applications for the search engines, including discovery of important news events, keyword recommendation and efficient keyword-to-advertisement mapping. We present new mechanisms for very fast search operations over the compressed time-series data, with specific focus on weblog data. An important contribution of this work is the derivation of optimally tight bounds on the Euclidean distance estimation between compressed sequences. Since our methodology is applicable to sequential data in general, the proposed technique is of independent interest. Additionally, our distance estimation strategy is not tied to a specific compression methodology, but can be applied on top of any orthonormal based compression technique (Fourier, Wavelet, PCA, etc). The experimental results indicate that the new optimal bounds lead to a significant improvement in the pruning power of search compared to previous state-of-the-art, in many cases eliminating more than 80 % of the candidate search sequences. 1
Positive Unlabeled Learning for Data Stream Classification.

Anonymization with Worst%2DCase Distribution%2DBased Background Knowledge

A Survey of Uncertain Data Algorithms and Applications.

Information discovery across multiple streams.
In this paper we address the issue of continuous keyword queries on multiple textual streams and explore techniques for extracting useful information from them. The paper represents, to our best knowledge, the first approach that performs keyword search on a multiplicity of textual streams. The scenario that we consider is quite intuitive; let&#039;s assume that a research or financial analyst is searching for information on a topic, continuously polling data from multiple (and possibly heterogeneous) text streams, such as RSS feeds, blogs, etc. The topic of interest can be
Embedding and Retrieving Private Metadata in Electrocardiograms.

Answering linear optimization queries with an approximate stream index.

Graph OLAP a multi%2Ddimensional framework for graph data analysis.

G%2DSESAME web tools for GO%2Dterm%2Dbased gene similarity analysis and knowledge discovery.

Efficient Method for Maximizing Bichromatic Reverse Nearest Neighbor.
Bichromatic reverse nearest neighbor (BRNN) has been extensively studied in spatial database literature. In this paper, we study a related problem called MaxBRNN: find an optimal region that maximizes the size of BRNNs. Such a problem has many real life applications, including the problem of finding a new server point that attracts as many customers as possible by proximity. A straightforward approach is to determine the BRNNs for all possible points that are not feasible since there are a large (or infinite) number of possible points. To the best of our knowledge, the fastest known method has exponential time complexity on the data size. Based on some interesting properties of the problem, we come up with an efficient algorithm called MaxOverlap. Extensive experiments are conducted to show that our algorithm is many times faster than the best-known technique. 1.
GConnect A Connectivity Index for Massive Disk%2Dresident Graphs.
The problem of connectivity is an extremely important one in the context of massive graphs. In many large communication networks, social networks and other graphs, it is desirable to determine the minimum-cut between any pair of nodes. The problem is well solved in the classical literature, since it is related to the maximum-flow problem, which is efficiently solvable. However, large graphs may often be disk resident, and such graphs cannot be efficiently processed for connectivity queries. This is because the minimum-cut problem is typically solved with the use of a variety of combinatorial and flow-based techniques which require random access to the underlying edges in the graph. In this paper, we propose to develop a connectivity index for massive-disk resident graphs. We will use an edgesampling based approach to create compressed representations of the underlying graphs. Since these compressed representations can be held in main memory, they can be used to derive efficient approximations for the minimum-cut problem. These compressed representations are then organized into a disk-resident index structure. We present experimental results which show that the resulting approach provides between two and three orders of magnitude more efficient query processing than a disk-resident approach at the expense of a small amount of accuracy. 1.
Introduction to special issue on social computing

Density%2Dbased clustering of data streams at multiple resolutions.

Online pairing of VoIP conversations.



Clustering on Complex Graphs.
Complex graphs, in which multi-type nodes are linked to each other, frequently arise in many important applications, such as Web mining, information retrieval, bioinformatics, and epidemiology. In this study, We propose a general framework for clustering on complex graphs. Under this framework, we derive a family of clustering algorithms including both hard and soft versions, which are capable of learning cluster patterns from complex graphs with various structures and statistical properties. We also establish the connections between the proposed framework and the traditional graph partitioning approaches. The experimental evaluation provides encouraging results to validate the proposed framework and algorithms.
Content%2Dbased filtering for efficient online materialized view maintenance.

Real%2Dtime new event detection for video streams.

Dual encryption for query integrity assurance.

Hierarchical%2C Parameter%2DFree Community Discovery.
Abstract. Given a large bipartite graph (like document-term, or userproduct graph), how can we find meaningful communities, quickly, and automatically? We propose to look for community hierarchies, with communities-within-communities. Our proposed method, the Context-specific Cluster Tree (CCT) finds such communities at multiple levels, with no user intervention, based on information theoretic principles (MDL). More specifically, it partitions the graph into progressively more refined subgraphs, allowing users to quickly navigate from the global, coarse structure of a graph to more focused and local patterns. As a fringe benefit, and also as an additional indication of its quality, it also achieves better compression than typical, non-hierarchical methods. We demonstrate its scalability and effectiveness on real, large graphs. 1
Fast computing reachability labelings for large graphs with high compression rate.
There are numerous applications that need to deal with a large graph and need to query reachability between nodes in the graph. A 2-hop cover can compactly represent the whole edge transitive closure of a graph in O(|V |  · |E | 1/2) space, and be used to answer reachability query efficiently. However, it is challenging to compute a 2-hop cover. The existing approaches suffer from either large resource consumption or low compression rate. In this paper, we propose a hierarchical partitioning approach to partition a large graph G into two subgraphs repeatedly in a top-down fashion. The unique feature of our approach is that we compute 2-hop cover while partitioning. In brief, in every iteration of top-down partitioning, we provide techniques to compute the 2-hop cover for connections between the two subgraphs first. A cover is computed to cut the graph into two subgraphs, which results in an overall cover with high compression for the entire graph G. Two approaches are proposed, namely a node-oriented approach and an edge-oriented approach. Our approach can efficiently compute 2-hop cover for a large graph with high compression rate. Our extensive experiment study shows that the 2-hop cover for a graph with 1,700,000 nodes and 169 billion connections can be obtained in less than 30 minutes with a compression rate about 40,000 using a PC.
Ownership protection of shape datasets with geodesic distance preservation.

Scalable Processing of Spatial Alarms.
Spatial alarms extend the idea of time-based alarms to the spatial dimension. Just as time-based alarms are set to remind us of the arrival of a future reference time point, spatial alarms are set on a spatial location of interest which the subscribers of the alarm will travel to sometime in the future. Spatial alarm processing requires meeting two demanding objectives: high accuracy, which ensures zero or very low alarm misses, and high scalability, which requires highly efficient and optimal processing of spatial alarms. In this paper we present a motion-aware framework, facilitated by two systematic methods, for scalable processing of spatial alarms. First, we introduce the concept of safe period to minimize the number of unnecessary spatial alarm evaluations, increasing the throughput and scalability of the system. We show that our safe period-based alarm evaluation techniques can significantly reduce the server load for spatial alarm processing compared to the periodic evaluation approach, while preserving the accuracy and timeliness of spatial alarms. Second, we develop a suite of spatial alarm grouping techniques based on spatial locality of the alarms and motion behavior of the mobile users, which reduces the safe period computation cost for spatial alarm evaluation at the server side. We evaluate the scalability and accuracy of our approach using a road network simulator and show that the proposed motion-aware safe period-based approach to spatial alarm processing offers significant performance enhancements for the alarm processing server while maintaining high accuracy of spatial alarms, especially compared to the conventional periodic alarm evaluation approach. 1.

Toward Predictive Failure Management for Distributed Stream Processing Systems.


Rights Protection of Trajectory Datasets.

Online Failure Forecast for Fault%2DTolerant Data Stream Processing.

On High Dimensional Indexing of Uncertain Data.

A Framework for Clustering Uncertain Data Streams.

Direct Discriminative Pattern Mining for Effective Classification.
Classification
Efficient Construction of Compact Shedding Filters for Data Stream Processing.

LOCUST An Online Analytical Processing Framework for High Dimensional Classification of Data Streams.

A Sampling%2DBased Approach to Information Recovery.
Abstract — There has been a recent resurgence of interest in research on noisy and incomplete data. Many applications require information to be recovered from such data. Ideally, an approach for information recovery should have the following features. First, it should be able to incorporate prior knowledge about the data, even if such knowledge is in the form of complex distributions and constraints for which no close-form solutions exist. Second, it should be able to capture complex correlations and quantify the degree of uncertainty in the recovered data, and further support queries over such data. The database community has developed a number of approaches for information recovery, but none is general enough to offer all above features. To overcome the limitations, we take a significantly more general approach to information recovery based on sampling. We apply sequential importance sampling, a technique from statistics that works for complex distributions and dramatically outperforms naive sampling when data is constrained. We illustrate the generality and efficiency of this approach in two application scenarios: cleansing RFID data, and recovering information from published data that has been summarized and randomized for privacy. I.
Fast Graph Pattern Matching.

Stop Chasing Trends Discovering High Order Models in Evolving Data.
Abstract — Many applications are driven by evolving data — patterns in web traffic, program execution traces, network event logs, etc., are often non-stationary. Building prediction models for evolving data becomes an important and challenging task. Currently, most approaches work by “chasing trends”, that is, they keep learning or updating models from the evolving data, and use these impromptu models for online prediction. In many cases, this proves to be both costly and ineffective — much time is wasted on re-learning recurring concepts, yet the classifier may remain one step behind the current trend all the time. In this paper, we propose to mine high-order models in evolving data. More often than not, there are a limited number of concepts, or stable distributions, in the data stream, and concepts switch between each other constantly. We mine all such concepts offline from a historical stream, and build high quality models for each of them. At run time, combining historical concept change patterns and cues provided by an online training stream, we find the most likely current concept and use its corresponding models to classify data in an unlabeled stream. The primary advantage of the high-order model approach is its high accuracy. Experiments show that in benchmark datasets, classification error of the highorder model is only a small fraction of that of the current best approaches. Another important benefit is that, unlike state-of-theart approaches, our approach does not require users to tune any parameters to achieve a satisfying result on streams of different characteristics. I.
Graph OLAP Towards Online Analytical Processing on Graphs.
RESEARCH INTERESTS I am generally interested in data mining, data warehousing and database systems. My current research focuses on modeling, managing and analyzing large-scale graph and information network data.
Dirichlet Process Based Evolutionary Clustering.
Evolutionary Clustering has emerged as an important research topic in recent literature of data mining, and solutions to this problem have found a wide spectrum of applications, particularly in social network analysis. In this paper, based on the recent literature on Dirichlet processes, we have developed two different and specific models as solutions to this problem: DPChain and HDP-EVO. Both models substantially advance the literature on evolutionary clustering in the sense that not only they both perform better than the existing literature, but more importantly they are capable of automatically learning the cluster numbers and structures during the evolution. Extensive evaluations have demonstrated the effectiveness and promise of these models against the state-of-the-art literature. 1
Evolutionary Clustering by Hierarchical Dirichlet Process with Hidden Markov State.
This paper studies evolutionary clustering, which is a recently hot topic with many important applications, noticeably in social network analysis. In this paper, based on the recent literature on Hierarchical Dirichlet Process (HDP) and Hidden Markov Model (HMM), we have developed a statistical model HDP-HTM that combines HDP with a Hierarchical Transition Matrix (HTM) based on the proposed Infinite Hierarchical Hidden Markov State model (iH2MS) as an effective solution to this problem. The HDP-HTM model substantially advances the literature on evolutionary clustering in the sense that not only it performs better than the existing literature, but more importantly it is capable of automatically learning the cluster numbers and structures and at the same time explicitly addresses the correspondence issue during the evolution. Extensive evaluations have demonstrated the effectiveness and promise of this solution against the state-of-the-art literature. 1
Time Sensitive Ranking with Application to Publication Search.

Multi%2DSpace%2DMapped SVMs for Multi%2Dclass Classification.

A Context%2DDriven Content Adaptation Planner for Improving Mobile Internet Accessibility.


Direct mining of discriminative and essential frequent patterns via model%2Dbased search tree.


Anonymizing transaction databases for publication.
This paper considers the problem of publishing “transaction data” for research purposes. Each transaction is an arbitrary set of items chosen from a large universe. Detailed transaction data provides an electronic image of one&#039;s life. This has two implications. One, transaction data are excellent candidates for data mining research. Two, use of transaction data would raise serious concerns over individual privacy. Therefore, before transaction data is released for data mining, it must be made anonymous so that data subjects cannot be re-identified. The challenge is that transaction data has no structure and can be extremely high dimensional. Traditional anonymization methods lose too much information on such data. To date, there has been no satisfactory privacy notion and solution proposed for anonymizing transaction data. This paper proposes one way to address this issue.
Forward Semi%2Dsupervised Feature Selection.

Outlier Detection with Uncertain Data.
In recent years, many new techniques have been developed for mining and managing uncertain data. This is because of the new ways of collecting data which has resulted in enormous amounts of inconsistent or missing data. Such data is often remodeled in the form of uncertain data. In this paper, we will examine the problem of outlier detection with uncertain data sets. The outlier detection problem is particularly challenging for the uncertain case, because the outlier-like behavior of a data point may be a result of the uncertainty added to the data point. Furthermore, the uncertainty added to the other data points may skew the overall data distribution in such a way that true outliers may be masked. Therefore, it is critical to be able to remove the effects of the uncertainty added both at the aggregate level as well as at the level of individual data points. In this paper, we will examine a density based approach to outlier detection, and show how to use it to remove the uncertainty from the underlying data. We present experimental results illustrating the effectiveness of the method. 1
Type%2DIndependent Correction of Sample Selection Bias via Structural Discovery and Re%2Dbalancing.
Sample selection bias is a common problem in many real world applications, where training data are obtained under realistic constraints that make them follow a different distribution from the future testing data. For example, in the application of hospital clinical studies, it is common practice to build models from the eligible volunteers as the training data, and then apply the model to the entire populations. Because these volunteers are usually not selected at random, the training set may not be drawn from the same distribution as the test set. Thus, such a dataset suffers from “sample selection bias ” or “covariate shift”. In the past few years, much work has been proposed to reduce sample selection bias, mainly by statically matching the distribution between training set and test set. But in this paper, we do not explore the different distributions directly. Instead, we propose
On Indexing High Demensional Data with Uncertainty.

Mining Sequence Classifiers for Early Prediction.
Supervised learning on sequence data, also known as sequence classification, has been well recognized as an important data mining task with many significant applications. Since temporal order is important in sequence data, in many critical applications of sequence classification such as medical diagnosis and disaster prediction, early prediction is a highly desirable feature of sequence classifiers. In early prediction, a sequence classifier should use a prefix of a sequence as short as possible to make a reasonably accurate prediction. To the best of our knowledge, early prediction on sequence data has not been studied systematically. In this paper, we identify the novel problem of mining sequence classifiers for early prediction. We analyze the problem and the challenges. As the first attempt to tackle the problem, we propose two interesting methods. The sequential classification rule (SCR) method mines a set of sequential classification rules as a classifier. A so-called early-prediction utility is defined and used to select features and rules. The generalized sequential decision tree (GSDT) method adopts a divide-and-conquer strategy to generate a classification model. We conduct an extensive empirical evaluation on several real data sets. Interestingly, our two methods achieve accuracy comparable to that of the stateof-the-art methods, but typically need to use only very short prefixes of the sequences. The results clearly indicate that early prediction is highly feasible and effective. 1
Proximity Tracking on Time%2DEvolving Bipartite Graphs.
Given an author-conference network that evolves over time, which are the conferences that a given author is most closely related with, and how do they change over time? Large time-evolving bipartite graphs appear in many settings, such as social networks, co-citations, market-basket analysis, and collaborative filtering. Our goal is to monitor (i) the centrality of an individual node (e.g., who are the most important authors?); and (ii) the proximity of two nodes or sets of nodes (e.g., who are the most important authors with respect to a particular conference?) Moreover, we want to do this efficiently and incrementally, and to provide “any-time ” answers. We propose pTrack and cTrack, which are based on random walk with restart, and use powerful matrix tools. Experiments on real data show that our methods are effective and efficient: the mining results agree with intuition; and we achieve up to 15∼176 times speed-up, without any quality loss. 1
A General Model for Multiple View Unsupervised Learning.
Multiple view data, which have multiple representations from different feature spaces or graph spaces, arise in various data mining applications such as information retrieval, bioinformatics and social network analysis. Since different representations could have very different statistical properties, how to learn a consensus pattern from multiple representations is a challenging problem. In this paper, we propose a general model for multiple view unsupervised learning. The proposed model introduces the concept of mapping function to make the different patterns from different pattern spaces comparable and hence an optimal pattern can be learned from the multiple patterns of multiple representations. Under this model, we formulate two specific models for
SPADE the system s declarative stream processing engine.
In this paper, we present Spade − the System S declarative stream processing engine. System S is a large-scale, distributed data stream processing middleware under development at IBM T. J. Watson Research Center. As a front-end for rapid application development for System S, Spade provides (1) an intermediate language for flexible composition of parallel and distributed data-flow graphs, (2) a toolkit of type-generic, built-in stream processing operators, that support scalar as well as vectorized processing and can seamlessly inter-operate with user-defined operators, and (3) a rich set of stream adapters to ingest/publish data from/to outside sources. More importantly, Spade automatically brings performance optimization and scalability to System S applications. To that end, Spade employs a code generation framework to create highly-optimized applications that run natively on the Stream Processing Core (SPC), the execution and communication substrate of System S, and take full advantage of other System S services. Spade allows developers to construct their applications with fine granular stream operators without worrying about the performance implications that might exist, even in a distributed system. Spade’s optimizing compiler automatically maps applications into appropriately sized execution units in order to minimize communication overhead, while at the same time exploiting available parallelism. By virtue of the scalability of the System S runtime and Spade’s effective code generation and optimization, we can scale applications to a large number of nodes. Currently, we can run Spade jobs on ≈ 500 processors within more than 100 physical nodes in a tightly connected cluster environment. Spade has been in use at IBM Research to create real-world streaming appli-
Mining significant graph patterns by leap search.

Temperature%2DAware Scheduling When is System%2DThrottling Good Enough%3F
Abstract Power-aware operating systems ensure that the system temperature does not exceed a threshold by utilizing system-throttling. In this technique, the system load (or alternatively, the clock speed) is scaled when the temperature hits this threshold. At other times, the system operates at maximum load. In this paper, we show that such simple system-throttling rules are in fact the best one can achieve under certain assumptions. We show that maintaining a constant operating speed (and thus temperature) always does more work than operating in alternating periods of cooling and heating. As a result, for certain settings and for a reasonable temperature model, we prove that system-throttling is the most effective temperature aware-scheduling. Naturally, these assumptions do not always hold; we also discuss the scenario when some of our assumptions are relaxed, and argue why one needs more complex scheduling algorithms in this case. 1 Introduction Energy and temperature management of processor systems is an increasingly important problem as the power consumption of these chips rises drastically with every new generation. At the same time, the rate of technological improvements in cooling systems has not been keeping pace [4]. Naturally, this has resulted in a large body of work that attempts to incorporate energy and temperature considerations into processor scheduling levels. Some of these are incorporated at the system level, where the on-chip architecture scales the speed of the processor if it is getting too hot. With advances in processor technology, this is also possible at the operating system level since most modern day processors have interfaces that allow the user to control its speed in real-time. The current processors by Intel, AMD, and IBM now allow a mechanism called dynamic voltage scaling (DVS) to control the clock speed of the processor [15] by varying the supply voltage. Most operating systems now also include commands which allow the user to access this interface (e.g., cpufreq in Linux).
Identifying the influential bloggers in a community.
Blogging becomes a popular way for a Web user to publish information on the Web. Bloggers write blog posts, share their likes and dislikes, voice their opinions, provide suggestions, report news, and form groups in Blogosphere. Bloggers form their virtual communities of similar interests. Activities happened in Blogosphere affect the external world. One way to understand the development on Blogosphere is to find influential blog sites. There are many non-influential blog sites which form the “the long tail”. Regardless of a blog site being influential or not, there are influential bloggers. Inspired by the high impact of the influentials in a physical community, we study a novel problem of identifying influential bloggers at a blog site. Active bloggers are not necessarily influential. Influential bloggers can impact fellow bloggers in various ways. In this paper, we discuss the challenges of identifying influential bloggers, investigate what constitutes influential bloggers, present a preliminary model attempting to quantify an influential blogger, and pave the way for building a robust model that allows for finding various types of the influentials. To illustrate these issues, we conduct experiments with data from a real-world blog site, evaluate multi-facets of the problem of identifying influential bloggers, and discuss unique challenges. We conclude with interesting findings and future work.
A holistic lexicon%2Dbased approach to opinion mining.
One of the important types of information on the Web is the opinions expressed in the user generated content, e.g., customer reviews of products, forum posts, and blogs. In this paper, we focus on customer reviews of products. In particular, we study the problem of determining the semantic orientations (positive, negative or neutral) of opinions expressed on product features in reviews. This problem has many applications, e.g., opinion mining, summarization and search. Most existing techniques utilize a list of opinion (bearing) words (also called opinion lexicon) for the purpose. Opinion words are words that express desirable (e.g., great, amazing, etc.) or undesirable (e.g., bad, poor, etc) states. These approaches, however, all have some major shortcomings. In this paper, we propose a holistic lexicon-based approach to solving the problem by exploiting external evidences and linguistic conventions of natural language expressions. This approach allows the system to handle opinion words that are context dependent, which cause major difficulties for existing algorithms. It also deals with many special words, phrases and language constructs which have impacts on opinions based on their linguistic patterns. It also has an effective function for aggregating multiple conflicting opinion words in a sentence. A system, called Opinion Observer, based on the proposed technique has been implemented. Experimental results using a benchmark product review data set and some additional reviews show that the proposed technique is highly effective. It outperforms existing methods significantly.
Approximate Frequent Itemset Mining In the Presence of Random Noise.

On static and dynamic methods for condensation%2Dbased privacy%2Dpreserving data mining.
In recent years, privacy-preserving data mining has become an important problem because of the large amount of personal data which is tracked by many business applications. In many cases, users are unwilling to provide personal information unless the privacy of sensitive information is guaranteed. In this paper, we propose a new framework for privacy-preserving data mining of multi-dimensional data. Previous work for privacy-preserving data mining uses a perturbation approach which reconstructs data distributions in order to perform the mining. Such an approach treats each dimension independently and therefore ignores the correlations between the different dimensions. In addition, it requires the development of a new distribution-based algorithm for each data mining problem, since it does not use the multi-dimensional records, but uses aggregate distributions of the data as input. This leads to a fundamental re-design of data mining algorithms. In this paper, we will develop a new and flexible approach for privacy-preserving data mining which does not require new problem-specific algorithms, since it maps the original data set into a new anonymized data set. These anonymized data closely match the characteristics of the original data including the correlations among the different dimensions. We will show how to extend the method to the case of data streams. We present empirical results illustrating the effectiveness of the method. We also show the efficiency of the method for data streams.
Correlating burst events on streaming stock market data.

A framework for condensation%2Dbased anonymization of string data.

Classifying Data Streams with Skewed Class Distributions and Concept Drifts.

Truth Discovery with Multiple Conflicting Information Providers on the Web.
The world-wide web has become the most important information source for most of us. Unfortunately, there is no guarantee for the correctness of information on the web. Moreover, different web sites often provide conflicting information on a subject, such as different specifications for the same product. In this paper we propose a new problem called Veracity, i.e., conformity to truth, which studies how to find true facts from a large amount of conflicting information on many subjects that is provided by various web sites. We design a general framework for the Veracity problem, and invent an algorithm called TruthFinder, which utilizes the relationships between web sites and their information, i.e., a web site is trustworthy if it provides many pieces of true information, and a piece of information is likely to be true if it is provided by many trustworthy web sites. Our experiments show that TruthFinder successfully finds true facts among conflicting information, and identifies trustworthy web sites better than the popular search engines.
peerTalk A Peer%2Dto%2DPeer Multiparty Voice%2Dover%2DIP System.

Top 10 algorithms in data mining.
Abstract This paper presents the top 10 data mining algorithms identified by the IEEE International Conference on Data Mining (ICDM) in December 2006: C4.5, k-Means, SVM, Apriori, EM, PageRank, AdaBoost, kNN, Naive Bayes, and CART. These top 10 algorithms are among the most influential data mining algorithms in the research community. With each algorithm, we provide a description of the algorithm, discuss the impact of the algorithm, and review current and further research on the algorithm. These 10 algorithms cover classification,
LeeWave level%2Dwise distribution of wavelet coefficients for processing kNN queries over distributed streams.

Fast Monitoring Proximity and Centrality on Time%2Devolving Bipartite Graphs.

Incremental tensor analysis Theory and applications.

Storage optimization for large%2Dscale distributed stream%2Dprocessing systems.

DAWN an efficient framework of DCT for data with error estimation.

Graph Partitioning Based on Link Distributions.
Existing graph partitioning approaches are mainly based on optimizing edge cuts and do not take the distribution of edge weights (link distribution) into consideration. In this paper, we propose a general model to partition graphs based on link distributions. This model formulates graph partitioning under a certain distribution assumption as approximating the graph affinity matrix under the corresponding distortion measure. Under this model, we derive a novel graph partitioning algorithm to approximate a graph affinity matrix under various Bregman divergences, which correspond to a large exponential family of distributions. We also establish the connections between edge cut objectives and the proposed model to provide a unified view to graph partitioning.
TS%2DTrees A Non%2DAlterable Search Tree Index for Trustworthy Databases on Write%2DOnce%2DRead%2DMany %28WORM%29 Storage.

An Efficient Online Tool to Search Top%2DN Genes with Similar Biological Functions in Gene Ontology Database.

On Temperature%2DAware Scheduling for Single%2DProcessor Systems.
Abstract. Power-aware operating systems/processor controllers ensure that the system temperature does not exceed a threshold by utilizing system-throttling, where the clock speed is scaled to an equilibrium load. We denote this as the Constant policy, and compare against Zig-Zag policies that alternate between phases of cooling and heating. In this paper, we characterize and calculate the best possible Zig-Zag policy, and argue that simple system-throttling rules are often optimal. In reality, however, the system design often forces us to implement Zig-Zag policies. In particular, we consider the case where the processor can operate only at a few discrete states; thus it is required to alternate between cooling and heating phases. In such a setting, we develop an algorithm that outperforms all other Zig-Zag policies, and present computational experiments emphasizing the performance of our algorithm. 1
Object Distinction Distinguishing Objects with Identical Names.

SAO A Stream Index for Answering Linear Optimization Queries.

A Load Shedding Framework and Optimizations for M%2Dway Windowed Stream Joins.
Tuple dropping, though commonly used for load shedding in most stream operations, is inadequate for m-way, windowed stream joins. The join output rate can be overly reduced because it fails to exploit the time correlations likely to exist among interrelated streams. In this paper, we introduce GrubJoin: an adaptive, m-way, windowed stream join that effectively performs time correlation-aware CPU load shedding. GrubJoin maximizes the output rate by achieving nearoptimal window harvesting, which picks only the most profitable window segments for the join. Due to combinatorial explosion of possible m-way join sequences involving window segments, m-way, windowed stream joins pose several unique challenges. We focus on addressing two of them: (1) How can we quickly determine the optimal window harvesting configuration for any m-way, windowed stream join? (2) How can we monitor and learn the time correlations among the streams with high accuracy and minimal overhead? To tackle these challenges, we formalize window harvesting as an optimization problem, develop greedy heuristics to determine nearoptimal window harvesting configurations and use approximation techniques to capture the time correlations. Our experimental results show that GrubJoin is vastly superior to tuple dropping when time correlations exist and is equally effective when time correlations are nonexistent. 1
Adaptive Load Diffusion for Multiway Windowed Stream Joins.

Lira Lightweight%2C Region%2Daware Load Shedding in Mobile CQ Systems.
To provide high-quality results for location-based, continual queries (CQs) in a mobile system, the query processor usually demands receiving frequent position updates from the mobile nodes. However, processing frequent updates often causes the query processor to become overloaded, under which updates must be dropped randomly, bringing down the query-result accuracy and negating the benefits of frequent updates. In this paper, we develop LIRA − a lightweight, region-aware load-shedding technique for preventively reducing the position-update load of a query processor, while maintaining high-quality query results. Instead of receiving too many updates and then randomly dropping some of them, LIRA uses a region-aware partitioning mechanism to identify the most beneficial shedding regions to cut down the position updates sent by the mobile nodes within those regions. Based on the densities of mobile nodes and queries in a region, LIRA judiciously applies different amounts of update reduction for different regions, aiming to minimize the negative impacts of load shedding on query-result accuracy. Experimental results show that LIRA is vastly superior to random update dropping and clearly outperforms other alternatives that do not possess region-aware load-shedding capabilities. Moreover, due to its lightweight nature, LIRA introduces very little overhead. 1
A Load Shedding Framework and Optimizations for M%2Dway Windowed Stream Joins.
Tuple dropping, though commonly used for load shedding in most stream operations, is inadequate for m-way, windowed stream joins. The join output rate can be overly reduced because it fails to exploit the time correlations likely to exist among interrelated streams. In this paper, we introduce GrubJoin: an adaptive, m-way, windowed stream join that effectively performs time correlation-aware CPU load shedding. GrubJoin maximizes the output rate by achieving nearoptimal window harvesting, which picks only the most profitable window segments for the join. Due to combinatorial explosion of possible m-way join sequences involving window segments, m-way, windowed stream joins pose several unique challenges. We focus on addressing two of them: (1) How can we quickly determine the optimal window harvesting configuration for any m-way, windowed stream join? (2) How can we monitor and learn the time correlations among the streams with high accuracy and minimal overhead? To tackle these challenges, we formalize window harvesting as an optimization problem, develop greedy heuristics to determine nearoptimal window harvesting configurations and use approximation techniques to capture the time correlations. Our experimental results show that GrubJoin is vastly superior to tuple dropping when time correlations exist and is equally effective when time correlations are nonexistent. 1
GString A Novel Approach for Efficient Search in Graph Databases.
Graphs are widely used for modeling complicated data, including chemical compounds, protein interactions, XML documents, and multimedia. Information retrieval against such data can be formulated as a graph search problem, and finding an efficient solution to the problem is essential for many applications. A popular approach is to represent both graphs and queries on graphs by sequences, thus converting graph search to subsequence matching. State-of-the-art sequencing methods work at the finest granularity – each node (or edge) in the graph will appear as an element in the resulting sequence. Clearly, such methods are not semantic conscious, and the resulting sequences are not only bulky but also prone to complexities arising from graph isomorphism and other problems in searching. In this paper, we introduce a novel sequencing method to capture the semantics of the underlying graph data. We find meaningful components in graph structures and use them as the most basic units in sequencing. It not only reduces the size of resulting sequences, but also enables semantic-based searching. In this paper, we base our approach on chemical compound databases, although it can be applied to searching other complicated graphs, such as protein structures. Experiments demonstrate that our approach outperforms state-ofthe-art graph search methods. 1.
Mining Colossal Frequent Patterns by Core Pattern Fusion.
Extensive research for frequent-pattern mining in the past decade has brought forth a number of pattern mining algorithms that are both effective and efficient. However, the existing frequent-pattern mining algorithms encounter challenges at mining rather large patterns, called colossal frequent patterns, in the presence of an explosive number of frequent patterns. Colossal patterns are critical to many applications, especially in domains like bioinformatics. In this study, we investigate a novel mining approach called Pattern-Fusion to efficiently find a good approximation to the colossal patterns. With Pattern-Fusion, a colossal pattern is discovered by fusing its small core patterns in one step, whereas the incremental pattern-growth mining strategies, such as those adopted in Apriori and FP-growth, have to examine a large number of mid-sized ones. This property distinguishes Pattern-Fusion from all the existing frequent pattern mining approaches and draws a new mining methodology. Our empirical studies show that, in cases where current mining algorithms cannot proceed, Pattern-Fusion is able to mine a result set which is a close enough approximation to the complete set of the colossal patterns, under a quality evaluation model proposed in this paper. 1
Community Learning by Graph Approximation.
Learning communities from a graph is an important problem in many domains. Different types of communities can be generalized as link-pattern based communities. In this paper, we propose a general model based on graph approximation to learn link-pattern based community structures from a graph. The model generalizes the traditional graph partitioning approaches and is applicable to learning various community structures. Under this model, we derive a family of algorithms which are flexible to learn various community structures and easy to incorporate the prior knowledge of the community structures. Experimental evaluation and theoretical analysis show the effectiveness and great potential of the proposed model and algorithms. 1
Efficient Discovery of Frequent Approximate Sequential Patterns.
We propose an efficient algorithm for mining frequent approximate sequential patterns under the Hamming distance model. Our algorithm gains its efficiency by adopting a “break-down-and-build-up ” methodology. The “breakdown” is based on the observation that all occurrences of a frequent pattern can be classified into groups, which we call strands. We developed efficient algorithms to quickly mine out all strands by iterative growth. In the “build-up” stage, these strands are grouped up to form the support sets from which all approximate patterns would be identified. A salient feature of our algorithm is its ability to grow the frequent patterns by iteratively assembling building blocks of significant sizes in a local search fashion. By avoiding incremental growth and global search, we achieve greater efficiency without losing the completeness of the mining result. Our experimental studies demonstrate that our algorithm is efficient in mining globally repeating approximate sequential patterns that would have been missed by existing methods. 1
Toward Self%2DManaged Media Stream Processing Service Overlays.

Relational clustering by symmetric convex coding.
Relational data appear frequently in many machine learning applications. Relational data consist of the pairwise relations (similarities or dissimilarities) between each pair of implicit objects, and are usually stored in relation matrices and typically no other knowledge is available. Although relational clustering can be formulated as graph partitioning in some applications, this formulation is not adequate for general relational data. In this paper, we propose a general model for relational clustering based on symmetric convex coding. The model is applicable to all types of relational data and unifies the existing graph partitioning formulation. Under this model, we derive two alternative bound optimization algorithms to solve the symmetric convex coding under two popular distance functions, Euclidean distance and generalized I-divergence. Experimental evaluation and theoretical analysis show the effectiveness and great potential of the proposed model and algorithms. 1.
BridgeNet An Adaptive Multi%2DSource Stream Dissemination Overlay Network.

A graph%2Dbased approach to systematically reconstruct human transcriptional regulatory modules.

Storage Optimization for Large%2DScale Distributed Stream Processing Systems.

A graph%2Dbased approach to systematically reconstruct human transcriptional regulatory modules.

Truth discovery with multiple conflicting information providers on the web.
The world-wide web has become the most important information source for most of us. Unfortunately, there is no guarantee for the correctness of information on the web. Moreover, different web sites often provide conflicting information on a subject, such as different specifications for the same product. In this paper we propose a new problem called Veracity, i.e., conformity to truth, which studies how to find true facts from a large amount of conflicting information on many subjects that is provided by various web sites. We design a general framework for the Veracity problem, and invent an algorithm called TruthFinder, which utilizes the relationships between web sites and their information, i.e., a web site is trustworthy if it provides many pieces of true information, and a piece of information is likely to be true if it is provided by many trustworthy web sites. Our experiments show that TruthFinder successfully finds true facts among conflicting information, and identifies trustworthy web sites better than the popular search engines.
Time%2Ddependent event hierarchy construction.

On string classification in data streams.
String data has recently become important because of its use in a number of applications such as computational and molecular biology, protein analysis, and market basket data. In many cases, these strings contain a wide variety of substructures which may have physical significance for that application. For example, such substructures could represent important fragments of a DNA string or an interesting portion of a fraudulent transaction. In such a case, it is desirable to determine the identity, location, and extent of that substructure in the data. This is a much more difficult generalization of the classification problem, since the latter problem labels entire strings rather than deal with the more complex task of determining string fragments with a particular kind of behavior. The problem becomes even more complicated when different kinds of substrings show complicated nesting patterns. Therefore, we define a somewhat different problem which we refer to as the generalized classification problem. We propose a scalable approach based on hidden markov models for this problem. We show how to implement the generalized string classification procedure for very large data bases and data streams. We present experimental results over a number of large data sets and data streams.
A probabilistic framework for relational clustering.
Relational clustering has attracted more and more attention due to its phenomenal impact in various important applications which involve multi-type interrelated data objects, such as Web mining, search marketing, bioinformatics, citation analysis, and epidemiology. In this paper, we propose a probabilistic model for relational clustering, which also provides a principal framework to unify various important clustering tasks including traditional attributes-based clustering, semi-supervised clustering, co-clustering and graph clustering. The proposed model seeks to identify cluster structures for each type of data objects and interaction patterns between different types of objects. Under this model, we propose parametric hard and soft relational clustering algorithms under a large number of exponential family distributions. The algorithms are applicable to relational data of various structures and at the same time unifies a number of stat-of-the-art clustering algorithms: co-clustering algorithms, the k-partite graph clustering, and semi-supervised clustering based on hidden Markov random fields. 
GraphScope parameter%2Dfree mining of large time%2Devolving graphs.

gPrune A Constraint Pushing Framework for Graph Pattern Mining.
Abstract. In graph mining applications, there has been an increasingly strong urge for imposing user-specified constraints on the mining results. However, unlike most traditional itemset constraints, structural constraints, such as density and diameter of a graph, are very hard to be pushed deep into the mining process. In this paper, we give the first comprehensive study on the pruning properties of both traditional and structural constraints aiming to reduce not only the pattern search space but the data search space as well. A new general framework, called gPrune, is proposed to incorporate all the constraints in such a way that they recursively reinforce each other through the entire mining process. A new concept, Pattern-inseparable Data-antimonotonicity, is proposed to handle the structural constraints unique in the context of graph, which, combined with known pruning properties, provides a comprehensive and unified classification framework for structural constraints. The exploration of these antimonotonicities in the context of graph pattern mining is a significant extension to the known classification of constraints, and deepens our understanding of the pruning properties of structural graph constraints. 1
Visual Exploration of Genomic Data.
The widespread acceptance and uptake of Grid technology can only be achieved if it can be ensured that the security mechanisms needed to support Grid based collaborations are at least as strong as local security mechanisms. The predominant way in which security is currently addressed in the Grid community is through Public Key Infrastructures (PKI) to support authentication. Whilst PKIs address user identity issues, authentication does not provide fine grained control over what users are allowed to do on remote resources (authorisation). The Grid community have put forward numerous software proposals for authorisation infrastructures such as AKENTI [1], CAS [2], CARDEA [3], GSI [4], PERMIS [5,6,7] and VOMS [8,9]. It is clear that for the foreseeable future a collection of solutions will be the norm. To address this, the Global Grid Forum (GGF) have proposed a generic SAML based authorisation API which in principle should allow for fine grained control for authorised access to any Grid service. Experiences in applying and stress testing this API from a variety of different application domains are essential to give insight into the practical aspects of large scale usage of authorisation infrastructures. This paper presents experiences from the DTI funded BRIDGES project [10] and the JISC funded DyVOSE project [11] in using this API with Globus version 3.3 [12] and the PERMIS authorisation infrastructure. 
A General Framework for Mining Concept%2DDrifting Data Streams with Skewed Distributions.
In recent years, there have been some interesting studies on predictive modeling in data streams. However, most such studies assume relatively balanced and stable data streams but cannot handle well rather skewed (e.g., few positives but lots of negatives) and stochastic distributions, which are typical in many data stream applications. In this paper, we propose a new approach to mine data streams by estimating reliable posterior probabilities using an ensemble of models to match the distribution over under-samples of negatives and repeated samples of positives. We formally show some interesting and important properties of the proposed framework, e.g., reliability of estimated probabilities on skewed positive class, accuracy of estimated probabilities, efficiency and scalability. Experiments are performed on several synthetic as well as real-world datasets with skewed distributions, and they demonstrate that our framework has substantial advantages over existing approaches in estimation reliability and predication accuracy. 1
A System for Keyword Search on Textual Streams.

A System for Keyword Search on Textual Streams.

On Anonymization of String Data.

BLINKS ranked keyword searches on graphs.
Query processing over graph-structured data is enjoying a growing number of applications. A top-k keyword search query on a graph nds the top k answers according to some ranking criteria, where each answer is a substructure of the graph containing all query keywords. Current techniques for supporting such queries on general graphs suffer from several drawbacks, e.g., poor worst-case performance, not taking full advantage of indexes, and high memory requirements. To address these problems, we propose BLINKS, a bi-level indexing and query processing scheme for top-k keyword search on graphs. BLINKS follows a search strategy with provable performance bounds, while additionally exploiting a bi-level index for pruning and accelerating the search. To reduce the index space, BLINKS partitions a data graph into blocks: The bilevel index stores summary information at the block level to initiate and guide search among blocks, and more detailed information for each block to accelerate search within blocks. Our experiments show that BLINKS offers orders-of-magnitude performance improvement over existing approaches.
Resource%2Dadaptive real%2Dtime new event detection.

Challenges and Experience in Prototyping a Multi%2DModal Stream Analytic and Monitoring Application on System S.

Towards Graph Containment Search and Indexing.
Given a set of model graphs D and a query graph q, containment search aims to find all model graphs g ∈ D such that q contains g (q ⊇ g). Due to the wide adoption of graph models, fast containment search of graph data finds many applications in various domains. In comparison to traditional graph search that retrieves all the graphs containing q (q ⊆ g), containment search has its own indexing characteristics that have not yet been examined. In this paper, we perform a systematic study on these characteristics and propose a contrast subgraph-based indexing model, called cIndex. Contrast subgraphs capture the structure differences between model graphs and query graphs, and are thus perfect for indexing due to their high selectivity. Using a redundancy-aware feature selection process, cIndex can sort out a set of significant and distinctive contrast subgraphs and maximize its indexing capability. We show that it is NP-complete to choose the best set of indexing features, and our greedy algorithm can approximate the one-level optimal index within a ratio of 1 − 1/e. Taking this solution as a base indexing model, we further extend it to accommodate hierarchical indexing methodologies and apply data space clustering and sampling techniques to reduce the index construction time. The proposed methodology provides a general solution to containment search and indexing, not only for graphs, but also for any data with transitive relations as well. Experimental results on real test data show that cIndex achieves near-optimal pruning power on various containment search workloads, and confirms its obvious advantage over indices built for traditional graph search in this new scenario. 1.
CellSort High Performance Sorting on the Cell Processor.
In this paper we describe the design and implementation of CellSort − a high performance distributed sort algorithm for the Cell processor. We design CellSort as a distributed bitonic merge with a data-parallel bitonic sorting kernel. In order to best exploit the architecture of the Cell processor and make use of all available forms of parallelism to achieve good scalability, we structure CellSort as a three-tiered sort. The first tier is a SIMD (single-instruction multiple data) optimized bitonic sort, which sorts up to 128KB of items that cat fit into one SPE’s (a co-processor on Cell) local store. We design a comprehensive SIMDization scheme that employs data parallelism even for the most fine-grained steps of the bitonic sorting kernel. Our results show that, SIMDized bitonic sorting kernel is vastly superior to other alternatives on the SPE and performs up to 1.7 times faster compared to quick sort on 3.2GHz Intel Xeon. The second tier is an in-core bitonic merge optimized for cross-SPE data transfers via asynchronous DMAs, and sorts enough number of items that can fit into the cumulative space available on the local stores of the participating SPEs. We design data transfer and synchronization patters that minimize serial sections of the code by taking advantage of the high aggregate cross-SPE bandwidth available on Cell. Results show that, in-core bitonic sort scales well on the Cell processor with increasing number of SPEs, and performs up to 10 times faster with 16 SPEs compared to parallel quick sort on dual-3.2GHz Intel Xeon. The third tier is an out-of-core 1 bitonic merge which sorts large number of items stored in the main memory. Results show that, when properly implemented, distributed out-of-core bitonic sort on Cell can significantly outperform the asymptotically (average case) superior quick sort for large number of memory resident items (up to 4 times faster when sorting 0.5GB of data with 16 SPEs, compared to dual-3.2GHz Intel Xeon). 1 The term “out-of-core ” does not imply a disk-based sort in the context of this paper. However, relation to external sorting is strong (see Sections 2 and 3 for details).
Executing Stream Joins on the Cell Processor.
Low-latency and high-throughput processing are key requirements of data stream management systems (DSMSs). Hence, multi-core processors that provide high aggregate processing capacity are ideal matches for executing costly DSMS operators. The recently developed Cell processor is a good example of a heterogeneous multi-core architecture and provides a powerful platform for executing data stream operators with high-performance. On the down side, exploiting the full potential of a multi-core processor like Cell is often challenging, mainly due to the heterogeneous nature of the processing elements, the software managed local memory at the co-processor side, and the unconventional programming model in general. In this paper, we study the problem of scalable execution of windowed stream join operators on multi-core processors, and specifically on the Cell processor. By examining various aspects of join execution flow, we determine the right set of techniques to apply in order to minimize the sequential segments and maximize parallelism. Concretely, we show that basic windows coupled with low-overhead pointer-shifting techniques can be used to achieve efficient join window partitioning, column-oriented join window organization can be used to minimize scattered data transfers, delay-optimized double buffering can be used for effective pipelining, rateaware batching can be used to balance join throughput and tuple delay, and finally SIMD (single-instruction multipledata) optimized operator code can be used to exploit data parallelism. Our experimental results show that, following the design guidelines and implementation techniques outlined in this paper, windowed stream joins can achieve high scalability (linear in the number of co-processors) by making efficient use of the extensive hardware parallelism provided by the Cell processor (reaching data processing rates of ≈ 13 GB/sec) and significantly surpass the performance obtained form conventional high-end processors (supporting a combined input stream rate of 2000 tuples/sec using 15 minutes windows and without dropping any tuples, resulting in ≈ 8.3 times higher output rate compared to an SSE implementation on dual 3.2Ghz Intel Xeon).
Time Series Compressibility and Privacy.
In this paper we study the trade-offs between time series compressibility and partial information hiding and their fundamental implications on how we should introduce uncertainty about individual values by perturbing them. More specifically, if the perturbation does not have the same compressibility properties as the original data, then it can be detected and filtered out, reducing uncertainty. Thus, by making the perturbation “similar ” to the original data, we can both preserve the structure of the data better, while simultaneously making breaches harder. However, as data become more compressible, a fraction of the uncertainty can be removed if true values are leaked, revealing how they were perturbed. We formalize these notions, study the above trade-offs on real data and develop practical schemes which strike a good balance and can also be extended for on-the-fly data hiding in a streaming environment. 1.
Towards Graph Containment Search and Indexing.
Given a set of model graphs D and a query graph q, containment search aims to find all model graphs g ∈ D such that q contains g (q ⊇ g). Due to the wide adoption of graph models, fast containment search of graph data finds many applications in various domains. In comparison to traditional graph search that retrieves all the graphs containing q (q ⊆ g), containment search has its own indexing characteristics that have not yet been examined. In this paper, we perform a systematic study on these characteristics and propose a contrast subgraph-based indexing model, called cIndex. Contrast subgraphs capture the structure differences between model graphs and query graphs, and are thus perfect for indexing due to their high selectivity. Using a redundancy-aware feature selection process, cIndex can sort out a set of significant and distinctive contrast subgraphs and maximize its indexing capability. We show that it is NP-complete to choose the best set of indexing features, and our greedy algorithm can approximate the one-level optimal index within a ratio of 1 − 1/e. Taking this solution as a base indexing model, we further extend it to accommodate hierarchical indexing methodologies and apply data space clustering and sampling techniques to reduce the index construction time. The proposed methodology provides a general solution to containment search and indexing, not only for graphs, but also for any data with transitive relations as well. Experimental results on real test data show that cIndex achieves near-optimal pruning power on various containment search workloads, and confirms its obvious advantage over indices built for traditional graph search in this new scenario. 1.
Graph Indexing Tree   Delta g%3B%3D Grap.

A Distributed Infrastructure Supporting Personalized Services for the Mobile Web.

A new method to measure the semantic similarity of GO terms.

CrossClus user%2Dguided multi%2Drelational clustering.

Domain%2DDriven%2C Actionable Knowledge Discovery.

GrubJoin An Adaptive
Tuple dropping, though commonly used for load shedding in most stream operations, is inadequate for m-way, windowed stream joins. The join output rate can be overly reduced because it fails to exploit the time correlations likely to exist among interrelated streams. In this paper, we introduce GrubJoin: an adaptive, m-way, windowed stream join that effectively performs time correlation-aware CPU load shedding. GrubJoin maximizes the output rate by achieving nearoptimal window harvesting, which picks only the most profitable window segments for the join. Due to combinatorial explosion of possible m-way join sequences involving window segments, m-way, windowed stream joins pose several unique challenges. We focus on addressing two of them: (1) How can we quickly determine the optimal window harvesting configuration for any m-way, windowed stream join? (2) How can we monitor and learn the time correlations among the streams with high accuracy and minimal overhead? To tackle these challenges, we formalize window harvesting as an optimization problem, develop greedy heuristics to determine nearoptimal window harvesting configurations and use approximation techniques to capture the time correlations. Our experimental results show that GrubJoin is vastly superior to tuple dropping when time correlations exist and is equally effective when time correlations are nonexistent. 1
Approximate Query Processing in Cube Streams.

Anonymizing Classification Data for Privacy Preservation.
Abstract — Classification is a fundamental problem in data analysis. Training a classifier requires accessing a large collection of data. Releasing person-specific data, such as customer data or patient records, may pose a threat to individual’s privacy. Even after removing explicit identifying information such as Name and SSN, it is still possible to link released records back to their identities by matching some combination of non-identifying attributes such as {Sex, Zip, Birthdate}. A useful approach to combat such linking attacks, called k-anonymization [1], is anonymizing the linking attributes so that at least k released records match each value combination of the linking attributes. Previous work attempted to find an optimal k-anonymization that minimizes some data distortion metric. We argue that minimizing the distortion to the training data is not relevant to the classification goal that requires extracting the structure of predication on the “future ” data. In this paper, we propose a k-anonymization solution for classification. Our goal is to find a k-anonymization, not necessarily optimal in the sense of minimizing data distortion, that preserves the classification structure. We conducted intensive experiments to evaluate the impact of anonymization on the classification on future data. Experiments on real life data show that the quality of classification can be preserved even for highly restrictive anonymity requirements. Index Terms — Privacy protection, anonymity, security, integrity, data mining, classification, data sharing
ASAP An Adaptive Sampling Approach to Data Collection in Sensor Networks.
Abstract — One of the most prominent and comprehensive ways of data collection in sensor networks is to periodically extract raw sensor readings. This way of data collection enables complex analysis of data, which may not be possible with in-network aggregation or query processing. However, this flexibility in data analysis comes at the cost of power consumption. In this paper we develop ASAP − an adaptive sampling approach to energyefficient periodic data collection in sensor networks. The main idea behind ASAP is to use a dynamically changing subset of the nodes as samplers such that the sensor readings of the sampler nodes are directly collected, whereas the values of the non-sampler nodes are predicted through the use of probabilistic models that are locally and periodically constructed. ASAP can be effectively used to increase the network lifetime while keeping the quality of the collected data high, in scenarios where either the
Fragmental Proxy Caching for Streaming Multimedia Objects.

Handicapping attacker%27s confidence an alternative to k %2Danonymization.

CPU load shedding for binary stream joins.

DDDM2007 Domain Driven Data Mining.

Proceedings of the 2006 ACM CIKM International Conference on Information and Knowledge Management

Advances in Web Mining and Web Usage Analysis

Classification Spanning Private Databases.

ViCo an adaptive distributed video correlation system.
Many emerging applications such as video sensor monitoring can benefit from an on-line video correlation system, which can be used to discover linkages between different video streams in realtime. However, on-line video correlations are often resource-intensive where a single host can be easily overloaded. We present a novel adaptive distributed on-line video correlation system called ViCo. Unlike single stream processing, correlations between different video streams require a distributed execution system to observe a new correlation constraint that any two correlated data must be distributed to the same host. ViCo achieves three unique features: (1) correlation-awareness that ViCo can guarantee the correlation accuracy while spreading excessive workload on multiple hosts; (2) adaptability that the system can adjust algorithm behaviors and switch between different algorithms to adapt to dynamic stream environments; and (3) finegranularity that the workload of one resource-intensive correlation request can be divided and distributed among multiple hosts. We have implemented and deployed a prototype of ViCo on a commercial cluster system. Our experiment results using both real videos and synthetic workloads show that ViCo outperforms existing techniques for scaling-up the performance of video correlations.
Continuous keyword search on multiple text streams.
In this paper we address the issue of continuous keyword queries on multiple textual streams and explore techniques for extracting useful information from them. The paper represents, to our best knowledge, the first approach that performs keyword search on a multiplicity of textual streams. The scenario that we consider is quite intuitive; let&#039;s assume that a research or financial analyst is searching for information on a topic, continuously polling data from multiple (and possibly heterogeneous) text streams, such as RSS feeds, blogs, etc. The topic of interest can be
Resource Adaptive Periodicity Estimation of Streaming Data.

Multi%2Dquery SQL Progress Indicators.
Abstract. Recently, progress indicators have been proposed for SQL queries in RDBMSs. All previously proposed progress indicators consider each query in isolation, ignoring the impact simultaneously running queries have on each other’s performance. In this paper, we explore a multi-query progress indicator, which explicitly considers concurrently running queries and even queries predicted to arrive in the future when producing its estimates. We demonstrate that multi-query progress indicators can provide more accurate estimates than single-query progress indicators. Moreover, we extend the use of progress indicators beyond being a GUI tool and show how to apply multi-query progress indicators to workload management. We report on an initial implementation of a multi-query progress indicator in PostgreSQL and experiments with its use both for estimating remaining query execution time and for workload management. 1
Fast Computation of Reachability Labeling for Large Graphs.
There are numerous applications that need to deal with a large graph and need to query reachability between nodes in the graph. A 2-hop cover can compactly represent the whole edge transitive closure of a graph in O(|V |  · |E | 1/2) space, and be used to answer reachability query efficiently. However, it is challenging to compute a 2-hop cover. The existing approaches suffer from either large resource consumption or low compression rate. In this paper, we propose a hierarchical partitioning approach to partition a large graph G into two subgraphs repeatedly in a top-down fashion. The unique feature of our approach is that we compute 2-hop cover while partitioning. In brief, in every iteration of top-down partitioning, we provide techniques to compute the 2-hop cover for connections between the two subgraphs first. A cover is computed to cut the graph into two subgraphs, which results in an overall cover with high compression for the entire graph G. Two approaches are proposed, namely a node-oriented approach and an edge-oriented approach. Our approach can efficiently compute 2-hop cover for a large graph with high compression rate. Our extensive experiment study shows that the 2-hop cover for a graph with 1,700,000 nodes and 169 billion connections can be obtained in less than 30 minutes with a compression rate about 40,000 using a PC.
Mining%2C Indexing%2C and Similarity Search in Graphs and Complex Structures.

Dual Labeling Answering Graph Reachability Queries in Constant Time.
Graph reachability is fundamental to a wide range of applications, including XML indexing, geographic navigation, Internet routing, ontology queries based on RDF/OWL, etc. Many applications involve huge graphs and require fast answering of reachability queries. Several reachability labeling methods have been proposed for this purpose. They assign labels to the vertices, such that the reachability between any two vertices may be decided using their labels only. For sparse graphs, 2-hop based reachability labeling schemes answer reachability queries efficiently using relatively small label space. However, the labeling process itself is often too time consuming to be practical for large graphs. In this paper, we propose a novel labeling scheme for sparse graphs. Our scheme ensures that graph reachability queries can be answered in constant time. Furthermore, for sparse graphs, the complexity of the labeling process is almost linear, which makes our algorithm applicable to massive datasets. Analytical and experimental results show that our approach is much more efficient than stateof-the-art approaches. Furthermore, our labeling method also provides an alternative scheme to tradeoff query time for label space, which further benefits applications that use tree-like graphs. 1
Searching Substructures with Superimposed Distance.
Efficient indexing techniques have been developed for the exact and approximate substructure search in large scale graph databases. Unfortunately, the retrieval problem of structures with categorical or geometric distance constraints is not solved yet. In this paper, we develop a method called PIS (Partition-based Graph Index and Search) to support similarity search on substructures with superimposed distance constraints. PIS selects discriminative fragments in a query graph and uses an index to prune the graphs that violate the distance constraints. We identify a criterion to distinguish the selectivity of fragments in multiple graphs and develop a partition method to obtain a set of highly selective fragments, which is able to improve the pruning performance. Experimental results show that PIS is effective in processing real graph queries. 1
Window%2Dbased Tensor Analysis on High%2Ddimensional and Multi%2Daspect Streams.
Data stream values are often associated with multiple aspects. For example, each value from environmental sensors may have an associated type (e.g., temperature, humidity, etc) as well as location. Aside from timestamp, type and location are the two additional aspects. How to model such streams? How to simultaneously find patterns within and across the multiple aspects? How to do it incrementally in a streaming fashion? In this paper, all these problems are addressed through a general data model, tensor streams, and an effective algorithmic framework, window-based tensor analysis (WTA). Two variations of WTA, independentwindow tensor analysis (IW) and moving-window tensor analysis (MW), are presented and evaluated extensively on real datasets. Finally, we illustrate one important application, Multi-Aspect Correlation Analysis (MACA), which uses WTA and we demonstrate its effectiveness on an environmental monitoring application. 1
Local Correlation Tracking in Time Series.
We address the problem of capturing and tracking local correlations among time evolving time series. Our approach is based on comparing the local auto-covariance matrices (via their spectral decompositions) of each series and generalizes the notion of linear cross-correlation. In this way, it is possible to concisely capture a wide variety of local patterns or trends. Our method produces a general similarity score, which evolves over time, and accurately reflects the changing relationships. Finally, it can also be estimated incrementally, in a streaming setting. We demonstrate its usefulness, robustness and efficiency on a wide range of real datasets. 1
Discovering Partial Orders in Binary Data.

Finding %22Who Is Talking to Whom%22 in VoIP Networks via Progressive Stream Clustering.

LOCI Load Shedding through Class%2DPreserving Data Acquisition.

AC%2DClose Efficiently Mining Approximate Closed Itemsets by Core Pattern Recovery.
Recent studies have proposed methods to discover approximate frequent itemsets in the presence of random noise. By relaxing the rigid requirement of exact frequent pattern mining, some interesting patterns, which would previously be fragmented by exact pattern mining methods due to the random noise or measurement error, are successfully recovered. Unfortunately, a large number of “uninteresting ” candidates are explored as well during the mining process, as a result of the relaxed pattern mining methodology. This severely slows down the mining process. Even worse, it is hard for an end user to distinguish the recovered interesting patterns from these uninteresting ones. In this paper, we propose an efficient algorithm AC-Close to recover the approximate closed itemsets from “core patterns”. By focusing on the so-called core patterns, integrated with a top-down mining and several effective pruning strategies, the algorithm narrows down the search space to those potentially interesting ones. Experimental results show that AC-Close substantially outperforms the previously proposed method in terms of efficiency, while delivers a similar set of interesting recovered patterns. 1.
Spectral clustering for multi%2Dtype relational data.
Clustering on multi-type relational data has attracted more and more attention in recent years due to its high impact on various important applications, such as Web mining, e-commerce and bioinformatics. However, the research on general multi-type relational data clustering is still limited and preliminary. The contribution of the paper is three-fold. First, we propose a general model, the collective factorization on related matrices, for multi-type relational data clustering. The model is applicable to relational data with various structures. Second, under this model, we derive a novel algorithm, the spectral relational clustering, to cluster multi-type interrelated data objects simultaneously. The algorithm iteratively embeds each type of data objects into low dimensional spaces and benefits from the interactions among the hidden structures of different types of data objects. Extensive experiments demonstrate the promise and effectiveness of the proposed algorithm. Third, we show that the existing spectral clustering algorithms can be considered as the special cases of the proposed model and algorithm. This demonstrates the good theoretic generality of the proposed model and algorithm. 1.

A general framework for accurate and fast regression by data summarization in random decision trees.


Global distance%2Dbased segmentation of trajectories.
This work introduces distance-based criteria for segmentation of object trajectories. Segmentation leads to simplification of the original objects into smaller, less complex primitives that are better suited for storage and retrieval purposes. Previous work on trajectory segmentation attacked the problem locally, segmenting separately each trajectory of the database. Therefore, they did not directly optimize the inter-object separability, which is necessary for mining operations such as searching, clustering, and classification on large databases. In this paper we analyze the trajectory segmentation problem from a global perspective, utilizing data aware distance-based optimization techniques, which optimize pairwise distance estimates hence leading to more efficient object pruning. We first derive exact solutions of the distance-based formulation. Due to the intractable complexity of the exact solution, we present an approximate, greedy solution that exploits forward searching of locally optimal solutions. Since the greedy solution also imposes a prohibitive computational cost, we also put forward more lightweight variance-based segmentation techniques, which intelligently “relax ” the pairwise distance only in the areas that affect the least the mining operations.
Suppressing model overfitting in mining concept%2Ddrifting data streams.

GPLAG detection of software plagiarism by program dependence graph analysis.
Along with the blossom of open source projects comes the convenience for software plagiarism. A company, if less self-disciplined, may be tempted to plagiarize some open source projects for its own products. Although current plagiarism detection tools appear sufficient for academic use, they are nevertheless short for fighting against serious plagiarists. For example, disguises like statement reordering and code insertion can effectively confuse these tools. In this paper, we develop a new plagiarism detection tool, called GPlag, which detects plagiarism by mining program dependence graphs (PDGs). A PDG is a graphic representation of the data and control dependencies within a procedure. Because PDGs are nearly invariant during plagiarism, GPlag is more effective than state-of-the-art tools for plagiarism detection. In order to make GPlag scalable to large programs, a statistical lossy filter is proposed to prune the plagiarism search space. Experiment study shows that GPlag is both effective and efficient: It detects plagiarism that easily slips over existing tools, and it usually takes a few seconds to find (simulated) plagiarism in programs having thousands of lines of code.
RIVA Indexing and Visualization of High%2DDimensional Data Via Dimension Reorderings.

Discovering Overlapping Communities of Named Entities.
Abstract. Although community discovery based on social network analysis has been studied extensively in the Web hyperlink environment, limited research has been done in the case of named entities in text documents. The cooccurrence of entities in documents usually implies some connections among them. Investigating such connections can reveal important patterns. In this paper, we mine communities among named entities in Web documents and text corpus. Most existing works on community discovery generate a partition of the entity network, assuming each entity belongs to one community. However, in the scenario of named entities, an entity may participate in several communities. For example, a person is in the communities of his/her family, colleagues, and friends. In this paper, we propose a novel technique to mine overlapping communities of named entities. This technique is based on triangle formation, expansion, and clustering with content similarity. Our experimental results show that the proposed technique is highly effective.
A framework for resource%2Daware knowledge discovery in data streams a holistic approach with its application to clustering.

A Framework for Clustering Massive Text and Categorical Data Streams.
Many applications such as news group filtering, text crawling, and document organization require real time clustering and segmentation of text data records. The categorical data stream clustering problem also has a number of applications to the problems of customer segmentation and real time trend analysis. We will present an online approach for clustering massive text and categorical data streams with the use of a statistical summarization methodology. We present results illustrating the effectiveness of the technique.
Optimal multi%2Dscale patterns in time series streams.
We introduce a method to discover optimal local patterns, which concisely describe the main trends in a time series. Our approach examines the time series at multiple time scales (i.e., window sizes) and efficiently discovers the key patterns in each. We also introduce a criterion to select the best window sizes, which most concisely capture the key oscillatory as well as aperiodic trends. Our key insight lies in learning an optimal orthonormal transform from the data itself, as opposed to using a predetermined basis or approximating function (such as piecewise constant, shortwindow Fourier or wavelets), which essentially restricts us to a particular family of trends. Our method lifts that limitation, while lending itself to fast, incremental estimation in a streaming setting. Experimental evaluation shows that our method can capture meaningful patterns in a variety of settings. Our streaming approach requires order of magnitude less time and space, while still producing concise and informative patterns. 1.
LinkClus Efficient Clustering via Heterogeneous Semantic Links.
Data objects in a relational database are cross-linked with each other via multi-typed links. Links contain rich semantic information that may indicate important relationships among objects. Most current clustering methods rely only on the properties that belong to the objects per se. However, the similarities between objects are often indicated by the links, and desirable clusters cannot be generated using only the properties of objects. In this paper we explore linkage-based clustering, in which the similarity between two objects is measured based on the similarities between the objects linked with them. In comparison with a previous study (SimRank) that computes links recursively on all pairs of objects, we take advantage of the power law distribution of links, and develop a hierarchical structure called SimTree to represent similarities in multi-granularity manner. This method avoids the high cost of computing and storing pairwise similarities but still thoroughly explore relationships among objects. An efficient algorithm is proposed to compute similarities between objects by avoiding pairwise similarity computations through merging computations that go through the same branches in the SimTree. Experiments show the proposed approach achieves high efficiency, scalability, and accuracy in clustering multi-typed linked objects. 1.
On%2DDemand Index for Efficient Structural Joins.

Feature%2Dbased similarity search in graph structures.
Similarity search of complex structures is an important operation in graph-related applications since exact matching is often too restrictive. In this article, we investigate the issues of substructure similarity search using indexed features in graph databases. By transforming the edge relaxation ratio of a query graph into the maximum allowed feature misses, our structural filtering algorithm can filter graphs without performing pairwise similarity computation. It is further shown that using either too few or too many features can result in poor filtering performance. Thus the challenge is to design an effective feature set selection strategy that could maximize the filtering capability. We prove that the complexity of optimal feature set selection is Ω(2 m) in the worst case, where m is the number of features for selection. In practice, we identify several criteria to build effective feature sets for filtering, and demonstrate that combining features with similar size and selectivity can improve the filtering and search performance significantly within a multi-filter composition framework. The proposed feature-based filtering concept can be generalized and applied to searching approximate non-consecutive sequences, trees, and other structured data as well. Categories and Subject Descriptors: H.2.4 [Database Management]: Systems – Query process-This is a preliminary release of an article accepted by ACM Transactions on Database Systems. The definitive version is currently in production at ACM and, when released, will supersede this version.
Structural Periodic Measures for Time%2DSeries Data.

Text Classification without Negative Examples Revisit.

Discovering Frequent Closed Partial Orders from Strings.
Abstract—Mining knowledge about ordering from sequence data is an important problem with many applications, such as bioinformatics, Web mining, network management, and intrusion detection. For example, if many customers follow a partial order in their purchases of a series of products, the partial order can be used to predict other related customers ’ future purchases and develop marketing campaigns. Moreover, some biological sequences (e.g., microarray data) can be clustered based on the partial orders shared by the sequences. Given a set of items, a total order of a subset of items can be represented as a string. A string database is a multiset of strings. In this paper, we identify a novel problem of mining frequent closed partial orders from strings. Frequent closed partial orders capture the nonredundant and interesting ordering information from string databases. Importantly, mining frequent closed partial orders can discover meaningful knowledge that cannot be disclosed by previous data mining techniques. However, the problem of mining frequent closed partial orders is challenging. To tackle the problem, we develop Frecpo (for Frequent closed partial order), a practically efficient algorithm for mining the complete set of frequent closed partial orders from large string databases. Several interesting pruning techniques are devised to speed up the search. We report an extensive performance study on both real data sets and synthetic data sets to illustrate the effectiveness and the efficiency of our approach. Index Terms—Frequent patterns, closed patterns, partial orders, strings, data mining. 1
A Framework for On%2DDemand Classification of Evolving Data Streams.

Incremental Processing of Continual Range Queries over Moving Objects.

A Framework for On%2DDemand Classification of Evolving Data Streams.

Processing Moving Queries over Moving Objects Using Motion%2DAdaptive Indexes.
Abstract—This paper describes a motion-adaptive indexing scheme for efficient evaluation of moving continual queries (MCQs) over moving objects. It uses the concept of motion-sensitive bounding boxes (MSBs) to model moving objects and moving queries. These bounding boxes automatically adapt their sizes to the dynamic motion behaviors of individual objects. Instead of indexing frequently changing object positions, we index less frequently changing object and query MSBs, where updates to the bounding boxes are needed only when objects and queries move across the boundaries of their boxes. This helps decrease the number of updates to the indexes. More importantly, we use predictive query results to optimistically precalculate query results, decreasing the number of searches on the indexes. Motion-sensitive bounding boxes are used to incrementally update the predictive query results. Furthermore, we introduce the concepts of guaranteed safe radius and optimistic safe radius to extend our motion-adaptive indexing scheme to evaluating moving continual k-nearest neighbor ðkNNÞ queries. Our experiments show that the proposed motion-adaptive indexing scheme is efficient for the evaluation of both moving continual range queries and moving continual kNN queries. Index Terms—Moving object databases, spatio-temporal indexing, continual queries. 1
Efficient Classification across Multiple Database Relations A CrossMine Approach.

Detection and Classification of Changes in Evolving Data Streams.

Catch the moment maintaining closed frequent itemsets over a data stream sliding window.
This paper considers the problem of mining closed frequent itemsets over a data stream  sliding window using limited memory space. We design a synopsis data structure to monitor  transactions in the sliding window so that we can output the current closed frequent  itemsets at any time. Due to time and memory constraints, the synopsis data structure cannot  monitor all possible itemsets. However, monitoring only frequent itemsets will make it  impossible to detect new itemsets when they become frequent. In this paper, we introduce  a compact data structure, the closed enumeration tree (CET), to maintain a dynamically  selected set of itemsets over a sliding window. The selected itemsets contain a boundary  between closed frequent itemsets and the rest of the itemsets. Concept drifts in a data  stream are reflected by boundary movements in the CET. In other words, a status change  of any itemset (e.g., from non-frequent to frequent) must occur through the boundary.
Query indexing with containment%2Dencoded intervals for efficient stream processing.

A Holistic Approach for Resource%2Daware Adaptive Data Stream Mining.

Supporting multi%2Dparty voice%2Dover%2DIP services with peer%2Dto%2Dpeer stream processing.
Multi-party voice-over-IP (MVoIP) services provide economical and natural group communication mechanisms for many emerging applications such as on-line gaming, distance collaboration, and tele-immersion. In this paper, we present a novel peer-to-peer (P2P) stream processing system called peerTalk to provide resource-efficient and failure-resilient MVoIP services. Different from previous work, our solution is fully distributed and self-organizing without requiring specialized servers or IP multicast support. Particularly, we decouple the stream processing in MVoIP services into two phases: (1) aggregation phase that mixes audio streams from active speakers into a single stream; and (2) distribution phase that distributes the mixed audio stream to all listeners. The decoupled model allows us to optimize and adapt the P2P stream mixing and distribution processes separately. Specifically, we can adaptively spread stream mixing workload among resource-constrained peer hosts according to current speaking activities. We have implemented a prototype of the peerTalk system and conducted experiments in real-world wide-area networks. The results show that peerTalk can achieve lower resource contention and better service quality than previous common solutions.
Rotation invariant indexing of shapes and line drawings.

Adaptive load shedding for windowed stream joins.
We present an adaptive load shedding approach for windowed stream joins. In contrast to the conventional approach of dropping tuples from the input streams, we explore the concept of selective processing for load shedding. We allow stream tuples to be stored in the windows and shed excessive CPU load by performing the join operations, not on the entire set of tuples within the windows, but on a dynamically changing subset of tuples that are learned to be highly beneficial. We support such dynamic selective processing through three forms of runtime adaptations: adaptation to input stream rates, adaptation to time correlation between the streams and adaptation to join directions. Our load shedding approach enables us to integrate utility-based load shedding with time correlation-based load shedding. Indexes are used to further speed up the execution of stream joins. Experiments are conducted to evaluate our adaptive load shedding in terms of output rate and utility. The results show that our selective processing approach to load shedding is very effective and significantly outperforms the approach that drops tuples from the input streams. 1
Integrating DCT and DWT for approximating cube streams.

Compact reachability labeling for graph%2Dstructured data.
Testing reachability between nodes in a graph is a well-known problem with many important applications, including knowledge representation, program analysis, and more recently, biological and ontology databases inferencing as well as XML query processing. Various approaches have been proposed to encode graph reachability information using node labeling schemes, but most existing schemes only work well for specific types of graphs. In this paper, we propose a novel approach, HLSS(Hybrid Labeling of Sub-Structures), which identifies different types of substructures within a graph and encodes them using techniques suitable to the characteristics of each of them. We implement HLSS with an efficient two-phase algorithm, where the first phase identifies and encodes strongly connected components as well as tree substructures, and the second phase encodes the remaining reachability relationships by compressing dense rectangular submatrices in the transitive closure matrix. For the important subproblem of finding densest submatrices, we demonstrate the hardness of the problem and propose several practical algorithms. Experiments show that HLSS handles different types of graphs well, while existing approaches fall prey to graphs with substructures they are not designed to handle. Finally, we also discuss how to update reachability labels when the graph is updated, and qualitatively show that HLSS supports more efficient updates than existing approaches. 1
Data Stream Mining and Resource Adaptive Computation.

Optimal Component Composition for Scalable Stream Processing.
Stream processing has become increasingly important with emergence of stream applications such as audio/video surveillance, stock price tracing, and sensor data analysis. A challenging problem is to provide optimal component composition in a distributed stream processing environment. The goal of optimal component composition is to achieve load balancing subject to multiple function, resource, and quality-of-service (QoS) constraints while composing stream applications. In this paper, we present an adaptive composition probing (ACP) approach to the problem. Different from previous work, ACP provides a new hybrid approach that combines distributed composition probing with coarse-grain global state management. Guided by the coarse-grain global state information, ACP selectively probes a subset of candidate components to discover an approximately optimal component composition. Further, ACP is self-tuning, which can adaptively adjust the number of probes to maintain a specified composition performance target (i.e., composition success rate) in a dynamic stream environment. While the optimal component composition problem is NP-hard, our ACP approach provides an adaptive polynomial approximation solution. We have conducted extensive simulation experiments to show the efficiency, scalability, and adaptability of the ACP approach by comparing with other alternative solutions. 1
Online Mining of Data Streams Applications%2C Techniques and Progress.

Top%2DDown Specialization for Information and Privacy Preservation.
Releasing person-specific data in its most specific state poses a threat to individual privacy. This paper presents a practical and efficient algorithm for determining a generalized version of data that masks sensitive information and remains useful for modelling classification. The generalization of data is implemented by specializing or detailing the level of information in a top-down manner until a minimum privacy requirement is violated. This top-down specialization is natural and efficient for handling both categorical and continuous attributes. Our approach exploits the fact that data usually contains redundant structures for classification. While generalization may eliminate some structures, other structures emerge to help. Our results show that quality of classification can be preserved even for highly restrictive privacy requirements. This work has great applicability to both public and private sectors that share information for mutual benefits and productivity. 1.
Text Classification without Labeled Negative Documents.

Effective Estimation of Posterior Probabilities Explaining the Accuracy of Randomized Decision Tree Approaches.

Combining Multiple Clusterings by Soft Correspondence.

A Border%2DBased Approach for Hiding Sensitive Frequent Itemsets.

Template%2DBased Privacy Preservation in Classification Problems.
Privacy preservation is an important issue in the release of data for mining purposes. The k-anonymity model has been introduced for protecting individual identification. Recent studies show that a more sophisticated model is necessary to protect the association of individuals to sensitive information. In this paper, we propose an (α, k)-anonymity model to protect both identifications and relationships to sensitive information in data. We discuss the properties of (α, k)-anonymity model. We prove that the optimal (α, k)anonymity problem is NP-hard. We first present an optimal globalrecoding method for the (α, k)-anonymity problem. Next we propose a local-recoding algorithm which is more scalable and result in less data distortion. The effectiveness and efficiency are shown by experiments. We also describe how the model can be extended to more general cases.
An Improved Categorization of Classifier%27s Sensitivity on Sample Selection Bias.
A recent paper categorizes classifier learning algorithms according to their sensitivity to a common type of sample selection bias where the chance of an example being selected into the training sample depends on its feature vector   but not (directly) on its class label y. A classifier learner is categorized as &#034;local&#034; if it is insensitive to this type of sample selection bias, otherwise, it is considered &#034;global&#034;. In that paper, the true model is not clearly distinguished from the model that the algorithm outputs. In their discussion of Bayesian classifiers, logistic regression and hard-margin support vector machines, the true model (or the model that generates the true class label for every example) is implicitly assumed to be contained in the model space of the learner, and the true class probabilities and model estimated class probabilities are assumed to asymptotically converge as the training data set size increases. However, in the discussion of naive Bayes, decision trees and soft-margin support vector machines, the model space is assumed not to contain the true model, and these three classification algorithms are instead argued to be &#034;global learners&#034;. Here we argue that most classifier learning algorithms including those just discussed may or may not be affected by sample selection bias; this will depend on the dataset as well as the heuristics or inductive bias implied by the classifier learning algorithm and their appropriateness to the particular dataset. We make use of our earlier experimental results and produce additional results to illustrate our claims.
Focused Community Discovery.
Although community discovery based on social network has been studied extensively in the Web hyperlink environment, limited research has been done in the case of Web documents. The co-occurrence of Words and entities in sentences and documents usually implies some connections among them. Studying such connections may reveal important relationships. In this paper, we investigate the cooccurrences of named entities in Web pages and blogs, and mine communities among those entities. We show that identifying communities in such an environment can be transformed into a graph clustering problem. A hierarchical clustering algorithm is then proposed, which exploits triangle structures within the graph and the mutual information between vertices. Our empirical study shows that the proposed algorithm is promising in discovering communities from Web documents.
Efficiently Mining Frequent Closed Partial Orders.

CSR Speaker Recognition from Compressed VoIP Packet Stream.

Mining Evolving Streams with Resource Adaptive Computation.

Cross%2Drelational clustering with user%27s guidance.

Co%2Dclustering by block value decomposition.
Collaborative filtering aims at predicting a test user’s ratings for new items by integrating other like-minded users ’ rating information. Traditional collaborative filtering methods usually suffer from two fundamental problems: sparsity and scalability. In this paper, we propose a novel framework for collaborative filtering by applying Orthogonal Nonnegative Matrix Tri-Factorization (ONMTF), which (1) alleviates the sparsity problem via matrix factorization; (2)solves the scalability problem by simultaneously clustering rows and columns of the user-item matrix. Experimental results on benchmark data sets are presented to show that our algorithm is indeed more tolerant against both sparsity and scalability, and achieves good performance in the meanwhile. 1
Pattern%2Dbased similarity search for microarray data.

Adaptive Load Diffusion for Stream Joins.
Abstract. Data stream processing has become increasingly important as many emerging applications call for sophisticated realtime processing over data streams, such as stock trading surveillance, network traffic monitoring, and sensor data analysis. Stream joins are among the most important stream processing operations, which can be used to detect linkages and correlations between different data streams. One major challenge in processing stream joins is to handle continuous, high-volume, and time-varying data streams under resource constraints. In this paper, we present a novel load diffusion system to enable scalable execution of resource-intensive stream joins using an ensemble of server hosts. The load diffusion is achieved by a simple correlation-aware stream partition algorithm. Different from previous work, the load diffusion system can (1) achieve fine-grained load sharing in the distributed stream processing system; and (2) produce exact query answers without missing any join results or generate duplicate join results. Our experimental results show that the load diffusion scheme can greatly improve the system throughput and achieve more balanced load distribution. 1
On Incremental Processing of Continual Range Queries for Location%2DAware Services and Applications.

A Multi%2Dmetric Index for Euclidean and Periodic Matching.

Fast Burst Correlation of Financial Data.
Abstract. We examine the problem of monitoring and identification of correlated burst patterns in multi-stream time series databases. Our methodology is comprised of two steps: a burst detection part, followed by a burst indexing step. The burst detection scheme imposes a variable threshold on the examined data and takes advantage of the skewed distribution that is typically encountered in many applications. The indexing step utilizes a memory-based interval index for effectively identifying the overlapping burst regions. While the focus of this work is on financial data, the proposed methods and data-structures can find applications for anomaly or novelty detection in telecommunications and network traffic, as well as in medical data. Finally, we manifest the real-time response of our burst indexing technique, and demonstrate the usefulness of the approach for correlating surprising volume trading events at the NY stock exchange. 1
A Two%2DLevel Distributed Architecture for Efficient Web Content Adaptation and Delivery.

Building Decision Trees on Records Linked through Key References.
We consider the classification problem where the data is given by a collection of tables related by a hierarchical structure of key references and class labels contained in the root table. Each parent table represents a many-to-many relationship type among its child tables. Such data are frequently found in relational databases, data warehouses, XML data, and biological databases. One solution is joining all tables into a universal table based on the recorded relationships, but it suffers from a significant blowup caused by many-to-many relationships. Another solution is treating the problem as relational learning, at the cost of increased complexity and degraded performance. We propose a novel method that builds exactly the same decision tree classifier as built from the joined table, but not the blowup required in the traditional approach. 1
Iterative Mining for Rules with Constrained Antecedents.

Loadstar A Load Shedding Scheme for Classifying Data Streams.
We consider the problem of resource allocation in mining multiple data streams. Due to the large volume and the high speed of streaming data, mining algorithms must cope with the e#ects of system overload. How to realize maximum mining benefits under resource constraints becomes a challenging task. In this paper, we propose a load shedding scheme for classifying multiple data streams. We focus on the following problems: i) how to classify data that are dropped by the load shedding scheme? and ii) how to decide when to drop data from a stream? We introduce a quality of decision (QoD) metric to measure the level of uncertainty in classification when exact feature values of the data are not available because of load shedding. A Markov model is used to predict the distribution of feature values and we make classification decisions using the predicted values and the QoD metric. Thus, resources are allocated among multiple data streams to maximize the quality of classification decisions. Furthermore, our load shedding scheme is able to learn and adapt to changing data characteristics in the data streams. Experiments on both synthetic data and real-life data show that our load shedding scheme is e#ective in improving the overall accuracy of classification under resource constraints. keywords: data mining, data streams, load shedding, classification, quality of decision, feature prediction, Markov model.
Mining Behavior Graphs for %22Backtrace%22 of Noncrashing Bugs.
Analyzing the executions of a buggy software program is essentially a data mining process. Although many interesting methods have been developed to trace crashing bugs (such as memory violation and core dumps), it is still difficult to analyze noncrashing bugs (such as logical errors). In this paper, we develop a novel method to classify the structured traces of program executions using software behavior graphs. By analyzing the correct and incorrect executions, we have made good progress at the isolation of program regions that may lead to the faulty executions. The classification framework is built on an integration of closed graph mining and SVM classification. More interestingly, suspicious regions are identified through the capture of the classification accuracy change, which is measured incrementally during program execution. Our performance study and case-based experiments show that our approach is both effective and efficient.
Near%2DNeighbor Search in Pattern Distance Spaces.

On Periodicity Detection and Structural Periodic Similarity.

On Variable Constraints in Privacy Preserving Data Mining.

Online Analysis of Community Evolution in Data Streams.

Pushing Feature Selection Ahead Of Join.
ABSTRACT 1 Current approaches for feature selection on multiple data sources need to join all data in order to evaluate features against the class label, thus are not scalable and involve unnecessary information leakage. In this paper, we present a way of performing feature selection through class propagation, eliminating the need of join before feature selection. We propagate a very compact data structure that provides enough information for selecting features to each data source, thus allowing features to be evaluated locally without looking at any other information. Our experiments confirmed that our algorithm is highly scalable while effectively preserving the data privacy.
Substructure Similarity Search in Graph Databases.
Advanced database systems face a great challenge raised by the emergence of massive, complex structural data in bioinformatics, chem-informatics, and many other applications. The most fundamental support needed in these applications is the efficient search of complex structured data. Since exact matching is often too restrictive, similarity search of complex structures becomes a vital operation that must be supported efficiently. In this paper, we investigate the issues of substructure similarity search using indexed features in graph databases. By transforming the edge relaxation ratio of a query graph into the maximum allowed missing features, our structural filtering algorithm, called Grafil, can filter many graphs without performing pairwise similarity computations. It is further shown that using either too few or too many features can result in poor filtering performance. Thus the challenge is to design an effective feature set selection strategy for filtering. By examining the effect of different feature selection mechanisms, we develop a multi-filter composition strategy, where each filter uses a distinct and complementary subset of the features. We identify the criteria to form effective feature sets for filtering, and demonstrate that combining features with similar size and selectivity can improve the filtering and search performance significantly. Moreover, the concept presented in Grafil can be applied to searching approximate non-consecutive sequences, trees, and other complicated structures as well. 1.
Loadstar Load Shedding in Data Stream Mining.
In this demo, we show that intelligent load shedding is essential in achieving optimum results in mining data streams under various resource constraints. The Loadstar system introduces load shedding techniques to classifying multiple data streams of large volume and high speed. Loadstar uses a novel metric known as the quality of decision (QoD) to measure the level of uncertainty in classification. Resources are then allocated to sources where uncertainty is high. To make optimum classification decisions and accurate QoD measurement, Loadstar relies on feature prediction to model the data dropped by the load shedding mechanism. Furthermore, Loadstar is able to adapt to the changing data characteristics in data streams. The system thus offers a nice solution to data mining with resource constraints. 1
Parameter Free Bursty Events Detection in Text Streams.

On Clustering Techniques for Change Diagnosis in Data Streams.

Efficient structural joins with on%2Dthe%2Dfly indexing.
Previous work on structural joins mostly focuses on maintaining o#ine indexes on disks. Most of them also require the elements in both sets to be sorted. In this paper, we study an on-the-fly, in-memory indexing approach to structural joins. There is no need to sort the elements or maintain indexes on disks. We identify the similarity between the structural join problem and the stabbing query problem, and extend a main memory-based indexing technique for stabbing queries to structural joins.
Adding the Temporal Dimension to Search %2D A Case Study in Publication Search.

Mining Data Streams.
Abstract: Mining data streams has raised a number of research challenges for the data mining community. These challenges include the limitations of computational resources, especially because mining streams of data most likely be done on a mobile device with limited resources. Also due to the continuality of data streams, the algorithm should have only one pass or less over the incoming data records. In this article, our Algorithm Output Granularity (AOG) approach in mining data streams is discussed. AOG is a novel adaptable approach that can cope with the challenging inherent features of data streams. We also show the results for AOG based clustering in a resource constrained environment.
On High Dimensional Projected Clustering of Data Streams.

Efficient Processing of Continual Range Queries for Location%2DAware Mobile Services.

An Improved Biclustering Method for Analyzing Gene Expression Profiles.

WebKDD 2005 web mining and web usage analysis post%2Dworkshop report.

Demand%2Ddriven frequent itemset mining using pattern structures.

WebKDD 2005 web mining and web usage analysis post%2Dworkshop report.

An effective and efficient algorithm for high%2Ddimensional outlier detection.

Proceedings of the 9th ACM SIGMOD Workshop on Research Issues in Data Mining and Knowledge Discovery

Text Classification by Labeling Words.
Traditionally, text classifiers are built from labeled training examples. Labeling is usually done manually by human experts (or the users), which is a labor intensive and time consuming process. In the past few years, researchers investigated various forms of semi-supervised learning to reduce the burden of manual labeling. In this paper, we propose a different approach. Instead of labeling a set of documents, the proposed method labels a set of representative words for each class. It then uses these words to extract a set of documents for each class from a set of unlabeled documents to form the initial training set. The EM algorithm is then applied to build the classifier. The key issue of the approach is how to obtain a set of representative words for each class. One way is to ask the user to provide them, which is difficult because the user usually can only give a few words (which are insufficient for accurate learning). We propose a method to solve the problem. It combines clustering and feature selection. The technique can effectively rank the words in the unlabeled set according to their importance. The user then selects/labels some words from the ranked list for each class. This process requires less effort than providing words with no help or manual labeling of documents. Our results show that the new method is highly effective and promising.
Monitoring Continual Range Queries.
This paper proposes a generic framework for monitoring continuous spatial queries over moving objects. The framework distinguishes itself from existing work by being the first to address the location update issue and to provide a common interface for monitoring mixed types of queries. Based on the notion of safe region, the client location update strategy is developed based on the queries being monitored. Thus, it significantly reduces the wireless communication and query reevaluation costs required to maintain the upto-date query results. We propose algorithms for query evaluation/reevaluation and for safe region computation in this framework. Enhancements are also proposed to take advantage of two practical mobility assumptions: maximum speed and steady movement. The experimental results show that our framework substantially outperforms the traditional periodic monitoring scheme in terms of monitoring accuracy and CPU time while achieving a close-to-optimal wireless communication cost. The framework also can scale up to a large monitoring system and is robust under various object mobility patterns. 1.
Shingle%2DBased Query Indexing for Location%2DBased Mobile E%2DCommerce.

Motion adaptive indexing for moving continual queries over moving objects.
This paper describes a motion adaptive indexing scheme for efficient evaluation of moving continual queries (MCQs) over moving objects. It uses the concept of motion-sensitive bounding boxes (MSBs) to model moving objects and moving queries. These bounding boxes automatically adapt their sizes to the dynamic motion behaviors of individual objects. Instead of indexing frequently changing object positions, we index less frequently changing object and query MSBs, where updates to the bounding boxes are needed only when objects and queries move across the boundaries of their boxes. This helps decrease the number of updates to the indexes. More importantly, we use predictive query results to optimistically precalculate query results, decreasing the number of searches on the indexes. Motion-sensitive bounding boxes are used to incrementally update the predictive query results. Our experiments show that the proposed motion adaptive indexing scheme is efficient for the evaluation of moving continual range queries.
Interval query indexing for efficient stream processing.

CrossMine Efficient Classification Across Multiple Database Relations.
Most of today&#039;s structured data is stored in relational databases. Such a database consists of multiple relations which are linked together conceptually via entity-relationship links in the design of relational database schemas. Multi-relational classification can be widely used in many disciplines, such as financial decision making, medical research, and geographical applications. However, most classification approaches only work on single &#034;flat&#034; data relations. It is usually difficult to convert multiple relations into a single flat relation without either introducing huge, undesirable &#034;universal relation&#034; or losing essential information. Previous works using Inductive Logic Programming approaches (recently also known as Relational Mining) have proven effective with high accuracy in multi-relational classification. Unfortunately, they suffer from poor scalability w.r.t. the number of relations and the number of attributes in databases.
A Condensation Approach to Privacy Preserving Data Mining.
been issued as a Research Report for early dissemination of its contents. In view of the transfer of copyright to the outside publisher, its distribution outside of IBM prior to publication should be limited to peer communications and specific requests. After outside publication, requests should be filled only by reprints or legally obtained copies of the article (e.g., payment of royalties). Copies may be requested from IBM T. J. Watson Research Center, P.
Mining Extremely Skewed Trading Anomalies.

Indexing Continual Range Queries for Location%2DAware Mobile Services.

Indexing Continual Range Queries with Covering Tiles for Fast Locating of Moving Objects.

CrossMine Efficient Classification Across Multiple Database Relations.
Most of today&#039;s structured data is stored in relational databases. Such a database consists of multiple relations which are linked together conceptually via entity-relationship links in the design of relational database schemas. Multi-relational classification can be widely used in many disciplines, such as financial decision making, medical research, and geographical applications. However, most classification approaches only work on single &#034;flat&#034; data relations. It is usually difficult to convert multiple relations into a single flat relation without either introducing huge, undesirable &#034;universal relation&#034; or losing essential information. Previous works using Inductive Logic Programming approaches (recently also known as Relational Mining) have proven effective with high accuracy in multi-relational classification. Unfortunately, they suffer from poor scalability w.r.t. the number of relations and the number of attributes in databases.
Bottom%2DUp Generalization A Data Mining Solution to Privacy Protection.
The well-known privacy-preserved data mining modifies existing data mining techniques to randomized data. In this paper, we investigate data mining as a technique for masking data, therefore, termed data mining based privacy protection. This approach incorporates partially the requirement of a targeted data mining task into the process of masking data so that essential structure is preserved in the masked data. The idea is simple but novel: we explore the data generalization concept from data mining as a way to hide detailed information, rather than discover trends and patterns. Once the data is masked, standard data mining techniques can be applied without modification. Our work demonstrated another positive use of data mining technology: not only can it discover useful patterns, but also mask private information. We consider the following privacy problem: a data holder wants to release a version of data for building classification models, but wants to protect against linking the released data to an external source for inferring sensitive information. We adapt an iterative bottom-up generalization from data mining to generalize the data. The generalized data remains useful to classification but becomes difficult to link to other sources. The generalization space is specified by a hierarchical structure of generalizations. A key is identifying the best generalization to climb up the hierarchy at each iteration. Enumerating all candidate generalizations is impractical. We present a scalable solution that examines at most one generalization in each iteration for each attribute involved in the linking. 1
Decision Tree Evolution Using Limited Number of Labeled Data Items from Drifting Data Streams.
Most previously proposed mining methods on data streams make an unrealistic assumption that “labelled” data stream is readily available and can be mined at anytime. However, in most real-world problems, labelled data streams are rarely immediately available. Due to this reason, models are reconstructed only when labelled data become available periodically. This passive stream mining model has several drawbacks. We propose a new concept of demand-driven active data mining. In active mining, the loss of the model is either continuously guessed without using any true class labels or estimated, whenever necessary, from a small number of instances whose actual class labels are verified by paying an affordable cost. When the estimated loss is more than a tolerable threshold, the model evolves by using a small number of instances with verified true class labels. Previous work on active mining concentrates on error guess and estimation. In this paper, we discuss several approaches on decision tree evolution. 1
Moment Maintaining Closed Frequent Itemsets over a Stream Sliding Window.
This paper considers the problem of mining closed frequent itemsets over a sliding window using limited memory space. We design a synopsis data structure to monitor transactions in the sliding window so that we can output the current closed frequent itemsets at any time. Due to time and memory constraints, the synopsis data structure cannot monitor all possible itemsets. However, monitoring only frequent itemsets will make it impossible to detect new itemsets when they become frequent. In this paper, we introduce a compact data structure, the closed enumeration tree (CET), to maintain a dynamically selected set of itemsets over a sliding-window. The selected itemsets consist of a boundary between closed frequent itemsets and the rest of the itemsets. Concept drifts in a data stream are reflected by boundary movements in the CET. In other words, a status change of any itemset (e.g., from non-frequent to frequent) must occur through the boundary. Because the boundary is relatively stable, the cost of mining closed frequent itemsets over a sliding window is dramatically reduced to that of mining transactions that can possibly cause boundary movements in the CET. Our experiments show that our algorithm performs much better than previous approaches.
On demand classification of data streams.
Current models of the classification problem do not e#ectively handle bursts of particular classes coming in at different times. In fact, the current model of the classification problem simply concentrates on methods for one-pass classification modeling of very large data sets. Our model for data stream classification views the data stream classification problem from the point of view of a dynamic approach in which simultaneous training and testing streams are used for dynamic classification of data sets. This model reflects real life situations e#ectively, since it is desirable to classify test streams in real time over an evolving training and test stream. The aim here is to create a classification system in which the training model can adapt quickly to the changes of the underlying data stream. In order to achieve this goal, we propose an on-demand classification process which can dynamically select the appropriate window of past training data to build the classifier. The empirical results indicate that the system maintains a high classification accuracy in an evolving data stream, while providing an e#cient solution to the classification task.
Analysis of Peer%2Dto%2DPeer Systems Workload Characterization and Effects on Traffic Cacheability.

Processing Continual Range Queries over Moving Objects Using VCR%2DBased Query Indexes.

Mining of Evolving Data Streams with Privacy Preservation.
Privacy preserving data mining is a novel research direction in data mining and statistical databases, where data mining algorithms are analyzed for the side-effects they incur in data privacy. There have been many studies on efficient discovery of frequent itemsets in privacy preserving data mining. However, it is nontrivial to maintain such discovered frequent itemsets because a database may allow frequent itemsets updates and such frequent itemsets may be turned into infrequent itemsets. In this paper, an incremental updating algorithm IPPFIM is proposed for efficient maintenance of discovered frequent itemsets when new transaction data are added to a transaction database in privacy preserving. The algorithm makes use of previous mining results to cut down the cost of finding new frequent itemsets in an updated database, the performance evaluation shows the efficiency of this method. Keyword: Data mining, privacy-preserving, incremental
VCR indexing for fast event matching for highly%2Doverlapping range predicates.

Active Mining of Data Streams.
Most previously proposed mining methods on data streams make an unrealistic assumption that “labelled” data stream is readily available and can be mined at anytime. However, in most real-world problems, labelled data streams are rarely immediately available. Due to this reason, models are reconstructed only when labelled data become available periodically. This passive stream mining model has several drawbacks. We propose a new concept of demand-driven active data mining. In active mining, the loss of the model is either continuously guessed without using any true class labels or estimated, whenever necessary, from a small number of instances whose actual class labels are verified by paying an affordable cost. When the estimated loss is more than a tolerable threshold, the model evolves by using a small number of instances with verified true class labels. Previous work on active mining concentrates on error guess and estimation. In this paper, we discuss several approaches on decision tree evolution. 1
Resource%2DAware Mining with Variable Granularities in Data Streams.
For data stream applications, both approximation and adaptability are important issues for effective mining. We explore in this paper a fundamental problem that how the limited resources, e.g., memory space and computation power, can be well utilized to produce accurate estimates. Two important features for tracking mined patterns with properly utilized resources are examined. The first issue is temporal granularity which refers to the phenomenon that as time advances, people are more interested in recent events, meaning that more resources can be utilized to explore more recent data with finer granularities. Second, with the mining task of discovering frequent temporal patterns, more resources are expected to be allocated to the processing of those borderline patterns whose statistics, e.g., occurrence frequencies, are close to the specified thresholdsoastohaveproperfrequentitemsetidentification. This feature is called mining with support count granularity. Consequently, algorithm RAM-DS (Resource-Aware Mining for Data Streams) is designed to not only reduce the memory required for data storage but also retain good approximation of target time series. Experimental results have shown that the memory required for storing significant wavelet coefficients is very small and the quality of approximation is stable when performing incremental data updates, indicating that algorithm RAM-DS is feasible and suitable for adaptive mining in data streams. 1
Graph Indexing A Frequent Structure%2Dbased Approach.
Graph has become increasingly important in modelling complicated structures and schemaless data such as proteins, chemical compounds, and XML documents. Given a graph query, it is desirable to retrieve graphs quickly from a large database via graph-based indices. In this paper, we investigate the issues of indexing graphs and propose a novel solution by applying a graph mining technique. Di#erent from the existing path-based methods, our approach, called gIndex, makes use of frequent substructure as the basic indexing feature. Frequent substructures are ideal candidates since they explore the intrinsic characteristics of the data and are relatively stable to database updates. To reduce the size of index structure, two techniques, size-increasing support constraint  and discriminative fragments, are introduced. Our performance study shows that gIndex has 10 times smaller index size, but achieves 3-10 times better performance in comparison with a typical path-based method, GraphGrep. The gIndex approach not only provides an elegant solution to the graph indexing problem, but also demonstrates how database indexing and query processing can benefit from data mining, especially frequent pattern mining. Furthermore, the concepts developed here can be applied to indexing sequences, trees, and other complicated structures as well.
BASS Approximate Search on Large String Databases.
In this paper, we study the problem on how to build an index structure for large string databases to efficiently support various types of string matching without the necessity of mapping the substrings to a numerical space (e.g., string B-tree and MRS-index) nor the restriction of in-memory practice (e.g., suffix tree and suffix array). Towards this goal, we propose a new indexing scheme, BASS-tree, to efficiently support general approximate substring match (in terms of certain symbol substitutions and misalignments) in sublinear time on a large string database. The key idea behind the design is that all positions in each string are grouped recursively into a fully balanced tree according to the similarities of the subsequent segments starting at those positions. Each node is labeled with a regular expression that describes the commonality of the substrings indexed through the subtree. Any search can then be properly directed to the portion in the database with a high potential of matching quickly. With the BASS-tree in place, wild card(s) in the query pattern can also be handled in a seamless way. In addition, search of a long pattern can be decomposed into a series of searches of short segments followed by a process to join the results. It has been demonstrated in our experiments that the potential performance improvement brought by BASS-tree is in an order of magnitude over alternative methods.
A Fast Algorithm for Subspace Clustering by Pattern Similarity.

A Framework for Projected Clustering of High Dimensional Data Streams.
The data stream problem has been studied extensively  in recent years, because of the great  ease in collection of stream data. The nature  of stream data makes it essential to use  algorithms which require only one pass over  the data. Recently, single-scan, stream analysis  methods have been proposed in this context. However,
On the temporal dimension of search.
Web search is probably the single most important application on the Internet. The most famous search techniques are perhaps the PageRank and HITS algorithms. These algorithms are motivated by the observation that a hyperlink from a page to another is an implicit conveyance of authority to the target page. They exploit this social phenomenon to identify quality pages, e.g., &#034;authority&#034; pages and &#034;hub&#034; pages. In this paper we argue that these algorithms miss an important dimension of the Web, the temporal dimension. The Web is not a static environment. It changes constantly. Quality pages in the past may not be quality pages now or in the future. These techniques favor older pages because these pages have many in-links accumulated over time. New pages, which may be of high quality, have few or no inlinks and are left behind. Bringing new and quality pages to users is important because most users want the latest information. Research publication search has exactly the same problem. This paper studies the temporal dimension of search in the context of research publication search. We propose a number of methods deal with the problem. Our experimental results show that these methods are highly effective.
Mining Surprising Periodic Patterns.
In this paper, we focus on mining surprising periodic patterns in a sequence of events. In many applications, e.g., computational biology, an infrequent pattern is still considered very significant if its actual occurrence frequency exceeds the prior expectation by a large margin. The traditional metric, such as support, is not necessarily the ideal model to measure this kind of surprising patterns because it treats all patterns equally in the sense that every occurrence carries the same weight towards the assessment of the significance of a pattern regardless of the probability of occurrence. A more suitable measurement,  information, is introduced to naturally value the degree of surprise of each occurrence of a pattern as a continuous and monotonically decreasing function of its probability of occurrence. This would allow patterns with vastly different occurrence probabilities to be handled seamlessly. As the accumulated degree of surprise of all repetitions of a pattern, the concept of information gain is proposed to measure the overall degree of surprise of the pattern within a data sequence. The bounded information gain property is identified to tackle the predicament caused by the violation of the downward closure  property by the information gain measure and in turn provides an efficient solution to this problem. Empirical tests demonstrate the efficiency and the usefulness of the proposed model.
Utility computing SLA management based upon business objectives.

Editorial State of the Transactions.


EIC Editorial.

EIC Editorial.


WAR Weighted Association Rules for Item Intensities.

Discovering High%2DOrder Periodic Patterns.
Discovery of periodic patterns in time series data has become an active research area with many applications. These patterns can be hierarchical in nature, where a higher level pattern may consist of repetitions of lower level patterns. Unfortunately, the presence of noise may prevent these higher level patterns from being recognized in the sense that two portions (of a data sequence) that support the same (high level) pattern may have di erent layouts of occurrences of basic symbols. There may not exist any common representation in terms of raw symbol combinations; and hence such (high level) pattern may not be expressed by any previous model (defined on raw symbols or symbol combinations) and would not be properly recognized by any existing method. In this paper, we propose a novel model, namely meta-pattern, to capture these high level patterns. As a more exible model, the number of potential meta-patterns could be very large. A substantial diculty lies on how to identify the proper pattern candidates. However, the well-known A priori property is not able to provide sufficient pruning power. A new property, namely component location property, is identified and used to conduct the candidate generation so that an ecient computation-based mining algorithm can be developed. Last but not least, we apply our algorithm to some real and synthetic sequences and some interesting patterns are discovered.
Enhanced Biclustering on Expression Data.
molecular biology, which provide a powerful tool by which the expression patterns of thousands of genes can be monitored simultaneously and are already producing huge amount of valuable data. The concept of bicluster was introduced by Cheng and Church (2000) to capture the coherence of a subset of genes and a subset of conditions. A set of heuristic algorithms were also designed to either find one bicluster or a set of biclusters, which consist of iterations of masking null values and discovered biclusters, coarse and fine node deletion, node addition, and the inclusion of inverted data. These heuristics inevitably suffer from some serious drawback. The masking of null values and discovered biclusters with random numbers may result in the phenomenon of random interference which in turn impacts the discovery of high quality biclusters. To address this issue and to further accelerate the biclustering process, we generalize the model of bicluster to incorporate null values and propose a probabilistic algorithm (FLOC) that can discover a set of k possibly overlapping biclusters simultaneously. Furthermore, this algorithm can easily be extended to support additional features that suit different requirements at virtually little cost. Experimental study on the yeast gene expression data shows that the FLOC algorithm can offer substantial improvements over the previously proposed algorithm.
Cross%2DFeature Analysis for Detecting Ad%2DHoc Routing Anomalies.

New Algorithms for Content%2DBased Publication%2DSubscription Systems.

Indexing Weighted%2DSequences in Large Databases.
We present an index structure for managing weighted sequences in large databases. A weighted-sequence is defined as a two-dimensional structure where each element in the sequence is associated with a weight. A series of network events, for instance, is a weighted-sequence in that each event has a timestamp. Querying a large sequence database by events&#039; occurrence patterns is a first step towards understanding the temporal causal relationships among the events. The index structure proposed in this paper enables us to efficiently retrieve from the database all subsequences, possibly non-contiguous, that match a given query sequence both by events and by weights. The index method also takes into consideration the non-uniform frequency distribution of events in the sequence data. In addition, our method finds a broad range of applications in indexing scientific data consisting of multiple numerical columns for discovery of correlations among these columns. For instance, indexing a DNA micro-array that records expression levels of genes under different conditions enables us to search for genes whose responses to various experimental perturbations follow a given pattern. We demonstrate, using real-world data sets, that our method is effective and efficient.
Building Text Classifiers Using Positive and Unlabeled Examples.
This paper studies the problem of building text classifiers using positive and unlabeled examples. The key feature of this problem is that there is no negative example for learning. Recently, a few techniques for solving this problem were proposed in the literature. These techniques are based on the same idea, which builds a classifier in two steps. Each existing technique uses a different method for each step. In this paper, we first introduce some new methods for the two steps, and perform a comprehensive evaluation of all possible combinations of methods of the two steps. We then propose a more principled approach to solving the problem based on a biased formulation of SVM, and show experimentally that it is more accurate than the existing techniques. 1.
MaPle A Fast Algorithm for Maximal Pattern%2Dbased Clustering.
mine different types of arbitrarily positioned and overlapping clusters of genetic data to find interesting patterns.
Is random model better%3F On its accuracy and efficiency.

Inductive Learning in Less Than One Sequential Data Scan.

Managing eBusiness on Demand SLA Contracts in Business Terms Using the Cross%2DSLA Execution Manager SAM.
It is imperative for a competitive e-business service provider to be positioned to manage the execution of its service level agreement (SLA) contracts in business terms (e.g., minimizing financial penalties for service-level violations, maximizing service-level measurement based customer satisfaction metrics). This paper briefly describes the design rationale of an integrated set of businessoriented service level management (SLM) technologies under development in the SAM project at IBM T.J. Watson Research Center. The e-business SLA execution manager SAM, (1) enables the provider to deploy an effective means of capturing and managing contractual SLA data as well as provider-facing non-contractual SLM data; (2) assists service personnel to prioritize the processing of action-demanding quality management alerts as per the provider&#039;s SLM objectives; and (3) automates the prioritization and execution management of approved SLM processes on behalf of the provider, including assigning SLM tasks to service personnel.
Mining concept%2Ddrifting data streams using ensemble classifiers.
Recently, mining data streams with concept drifts for actionable insights has become an important and challenging task for a wide range of applications including credit card fraud protection, target marketing, network intrusion detection, etc. Conventional knowledge discovery tools are facing two challenges, the overwhelming volume of the streaming data, and the concept drifts. In this paper, we propose a general framework for mining concept-drifting data streams using weighted ensemble classifiers. We train an ensemble of classification models, such as C4.5, RIPPER, naive Bayesian, etc., from sequential chunks of the data stream. The classifiers in the ensemble are judiciously weighted based on their expected classification accuracy on the test data under the time-evolving environment. Thus, the ensemble approach improves both the efficiency in learning the model and the accuracy in performing classification. Our empirical study shows that the proposed methods have substantial advantage over single-classifier approaches in prediction accuracy, and the ensemble framework is effective for a variety of classification models.
Applying data mining in investigating money laundering crimes.
In this paper, we study the problem of applying data mining to facilitate the investigation of money laundering crimes (MLCs). We have identified a new paradigm of problems--- that of automatic community generation based on uni-party data, the data in which there is no direct or explicit link information available. Consequently, we have proposed a new methodology for Link Discovery based on Correlation Analysis (LDCA). We have used MLC group model generation as an exemplary application of this problem paradigm, and have focused on this application to develop a specific method of automatic MLC group model generation using Hierarchical Composition Based (HCB) correlation in the LDCA methodology. A prototype called CORAL is implemented in the MLC group model generation application, and preliminary testing and evaluations based on a real MLC case data are reported. The contributions of this work are (1) identification of the uni-party data community generation problem paradigm, (2) proposal of a new methodology LDCA to solve for problems in this paradigm, (3) formulation of the MLC group model generation problem as an example of this paradigm, (4) application of the LDCA methodology to develop a specific solution to the MLC group model generation problem by introducing HCB correlation measure using fuzzy logic, and (5) development, evaluation, and testing of the CORAL prototype in a real MLC case data. Categories and Subject Descriptors
STAMP On Discovery of Statistically Important Pattern Repeats in Long Sequential Data.
In this paper, we focus on mining periodic patterns allowing some degree of imperfection in the form of random replacement from a perfect periodic pattern. In InfoMiner+, we proposed a new metric, namely generalized information gain, to identify patterns with events of vastly different occurrence frequencies and to adjust for the deviation from a pattern. In particular, a penalty is allowed to be associated with gaps between pattern occurrences. This is particularly useful in locating repeats in DNA sequences. In this paper, we present an effective mining algorithm, STAMP, to simultaneously mine significant patterns and the associated subsequences under the model of generalized information gain.
ViST A Dynamic Index Method for Querying XML Data by Tree Structures.
much research has been done in providing flexible query facilities to extract data from structured XML documents. In this paper, we propose ViST, a novel index structure for searching XML documents. By representing both XML documents and XML queries in structure-encoded sequences, we show that querying XML data is equivalent to finding subsequence matches. Unlike index methods that disassemble a query into multiple sub-queries, and then join the results of these sub-queries to provide the final answers, ViST uses tree structures as the basic unit of query to avoid expensive join operations. Furthermore, ViST provides a unified index on both content and structure of the XML documents, hence it has a performance advantage over methods indexing either just content or structure. ViST supports dynamic index update, and it relies solely on B    Trees without using any specialized data structures that are not well supported by DBMSs. Our experiments show that ViST is e#ective, scalable, and e#cient in supporting structural queries.
A Regression%2DBased Temporal Pattern Mining Scheme for Data Streams.
We devise in this paper a regression-based algorithm, called algorithm FTP-DS (Frequent Temporal Patterns of Data Streams), to mine frequent temporal patterns for data streams. While providing a general framework of pattern frequency counting, algorithm FTP-DS has two major features, namely one data scan for online statistics collection and regressionbased compact pattern representation. To attain the feature of one data scan, the data segmentation and the pattern growth scenarios are explored for the frequency counting purpose. Algorithm FTP-DS scans online transaction flows and generates candidate frequent patterns in real time. The second important feature of algorithm FTP-DS is on the regression-based compact pattern representation. Specifically, to meet the space constraint, we devise for pattern representation a compact ATF (standing for Accumulated Time and Frequency) form to aggregately comprise all the information required for regression analysis. In addition, we develop the techniques of the segmentation tuning and segment relaxation to enhance the functions of FTP-DS. With these features, algorithm FTP-DS is able to not only conduct mining with variable time intervals but also perform trend detection effectively. Synthetic data and a real dataset which contains net-
Cooperative TransCaching A System of Distributed Proxy Servers for Web Content Adaptation.

Scoring the Data Using Association Rules.
In many data mining applications, the objective is to select data cases of a target class.
Guest Editorial Text and Web Mining.

Replication for Load Balancing and Hot%2DSpot Relief on Proxy Web Caches with Hash Routing.

Editorial New AE Introduction.

Optimizing Index Allocation for Sequential Data Broadcasting in Wireless Mobile Computing.

Mining Asynchronous Periodic Patterns in Time Series Data.
Periodicy detection in time series data is a challenging problem of great importance in many applications.
Editorial AE Introduction.

Request Redirection Algorithms for Distributed Web Systems.

Data Mining How Research Meets Practical Development%3F
At the 2001 IEEE International Conference on Data Mining in San Jose, California on  November 29 - December 2, 2001, there was a panel discussion on how data mining research  meets practical development. One of the motivations for organizing the panel discussion was to  provide useful advice for industrial people to explore their directions in data mining development.
Advances in Knowledge Discovery and Data Mining

Pruning and Dynamic Scheduling of Cost%2DSensitive Ensembles.

Efficient query monitoring using adaptive multiple key hashing.

An Index Structure for Pattern Similarity Searching in DNA Microarray Dat.

Accelerating Approximate Subsequence Search on Large Protein Sequence Databases.

An Index Structure for Pattern Similarity Searching in DNA Microarray Dat.

Clustering Algorithms for Content%2DBased Publication%2DSubscription Systems.
We consider efficient communication schemes based on both network-supported and application-level multicast techniques for content-based publication-subscription systems. We show that the communication costs depend heavily on the network configurations, distribution of publications and subscriptions. We devise new algorithms and adapt existing partitional data clustering algorithms. These algorithms can be used to determine multicast groups with as much commonality as possible, based on the totality of subscribers&#039; interests. They perform well in the context of highly heterogeneous subscriptions, and they also scale well. An efficiency of 60% to 80% with respect to the ideal solution can be achieved with a small number of multicast groups (less than 100 in our experiments). Some of these same concepts can be applied to match publications to subscribers in real-time, and also to determine dynamically whether to unicast, multicast or broadcast information about the events over the network to the matched subscribers. We demonstrate the quality of our algorithms via simulation experiments.
A Fully Distributed Framework for Cost%2DSensitive Data Mining.
In this paper, we propose a fully distributed system (as compared to centralized and partially distributed systems) for cost-sensitive data mining. Experimental results have shown that this approach achieves higher accuracy than both the centralized and partially distributed learning methods, however, it incurs much less training time, neither communication nor computation overhead. 1.
delta%2DClusters Capturing Subspace Correlation in a Large Data Set.
Clustering has been an active research area of great practical importance for recent years. Most previous clustering models have focused on grouping objects with similar values on a (sub)set of dimensions (e.g., subspace cluster) and assumed that every object has an associated value on every dimension (e.g., bicluster). These existing cluster models may not always be adequate in capturing coherence exhibited among objects. Strong coherence may still exist among a set of objects (on a subset of attributes) even if they take quite different values on each attribute and the attribute values are not fully specified. This is very common in many applications including bio-informatics analysis as well as collaborative filtering analysis, where the data may be incomplete and subject to biases. In bio-informatics, a bicluster model has recently been proposed to capture coherence among a subset of the attributes. Here, we introduce a more general model, referred to as the ffi-cluster model, to capture coherence exhibited by a subset of objects on a subset of attributes, while allowing absent attribute values. A move-based algorithm (FLOC) is devised to efficiently produce a near-optimal clustering results. The ffi-cluster model takes the bicluster model as a special case, where the FLOC algorithm performs far superior to the bicluster algorithm. We demonstrate the correctness and efficiency of the ffi-cluster model and the FLOC algorithm on a number of real and synthetic data sets.
Progressive Modeling.
Presently, inductive learning is still performed in a frustrating batch process. The user has little interaction with the system and no control over the final accuracy and training time. If the accuracy of the produced model is too low, all the computing resources are misspent. In this paper, we propose a progressive modeling framework. In progressive modeling, the learning algorithm estimates online both the accuracy of the final model and remaining training time. If the estimated accuracy is far below expectation, the user can terminate training prior to completion without wasting further resources. If the user chooses to complete the learning process, progressive modeling will compute a model with expected accuracy in expected time. We describe one implementation of progressive modeling using ensemble of classifiers.
Mining Associations by Pattern Structure in Large Relational Tables.
Association rule mining aims at discovering patterns whose support is beyond a given threshold. Mining patterns composed of items described by an arbitrary subset of attributes in a large relational table represents a new challenge and has various practical applications, including the event management systems that motivated this work. The attribute combinations that define the items in a pattern provide the structural information of the pattern. Current association algorithms do not make full use of the structural information of the patterns: the information is either lost after it is encoded with attribute values, or is constrained by a given hierarchy or taxonomy. Pattern structures convey important knowledge about the patterns. In this paper, we present a novel architecture that organizes the mining space based on pattern structures. By exploiting the interrelationships among pattern structures, execution times for mining can be reduced significantly. This advantage is demonstrated by our experiments using both synthetic and real-life datasets.
InfoMiner  Mining Partial Periodic Patterns with Gap Penalties.
In this paper, we focus on mining periodic patterns allowing some degree of imperfection in the form of random replacement from a perfect periodic pattern. Information gain was proposed to identify patterns with events of vastly different occurrence frequencies and adjust for the deviation from a pattern. However, it does not take any penalty if there exists some gap between the pattern occurrences. In many applications, e.g., bio-informatics, it is important to identify subsequences that a pattern repeats perfectly (or near perfectly). As a solution, we extend the information gain measure to include a penalty for gaps between pattern occurrences. We call this measure as generalized information gain. Furthermore, we want to find subsequence S    such that for a pattern P , the generalized information gain of P in S    is high. This is particularly useful in locating repeats in DNA sequences. In this paper, we developed an effective mining algorithm, InfoMiner+, to simultaneously mine significant patterns and the associated subsequences.
Partially Supervised Classification of Text Documents.
We investigate the following problem: Given a set  of documents of a particular topic or class # , and a  large set # of mixed documents that contains documents  from class # and other types of documents,  identify the documents from class # in # . The key  feature of this problem is that there is no labeled non-  # document, which makes traditional machine learning  techniques inapplicable, as they all need labeled  documents of both classes. We call this problem partially  supervised classification. In this paper, we show  that this problem can be posed as a constrained optimization  problem and that under appropriate conditions,  solutions to the constrained optimization problem  will give good solutions to the partially supervised  classification problem. We present a novel technique  to solve the problem and demonstrate the effectiveness  of the technique through extensive experimentation.
Distributed data mining in a chain store database of short transactions.
In this paper, we broaden the horizon of traditional rule mining by introducing a new framework of causality rule mining in a distributed chain store database. Specifically, the causality rule explored in this paper consists of a sequence of triggering events and a set of consequential events, and is designed with the capability of mining non-sequential, intertransaction information. Hence, the causality rule mining provides a very general framework for rule derivation. Note, however, that the procedure of causality rule mining is very costly particularly in the presence of a huge number of candidate sets and a distributed database, and in our opinion, cannot be dealt with by direct extensions from existing rule mining methods. Consequently, we devise in this paper a series of level matching algorithms, including Level Matching (abbreviateally as LM), Level Matching with Selective Scan (abbreviatedly as LMS), and Distributed Level Matching (abbreviatedly as Distibuted LM), to minimize the computing cost needed for the distributed data mining of causality rules. In addition, the phenomena of time window constraints are also taken into consideration for the development of our algorithms. As a result of properly employing the technologies of level matching and selective scan, the proposed algorithms present good efficiency and scalability in the mining of local and global causality rules. Scale-up experiments show that the proposed algorithms scale well actions.


Efficient Filtering of Large DatasetA User%2DCentric Paradigm.

Mining Relationship between Triggering and Consequential Events in a Short Transaction Database.

Clustering by pattern similarity in large data sets.
Clustering is the process of grouping a set of objects into classes of similar objects. Although definitions of similarity vary from one clustering model to another, in most of these models the concept of similarity is based on distances, e.g., Euclidean distance or cosine distance. In other words, similar objects are required to have close values on at least a set of dimensions. In this paper, we explore a more general type of similarity. Under the pCluster model we proposed, two objects are similar if they exhibit a coherent pattern on a subset of dimensions. For instance, in DNA microarray analysis, the expression levels of two genes may rise and fall synchronously in response to a set of environmental stimuli. Although the magnitude of their expression levels may not be close, the patterns they exhibit can be very much alike. Discovery of such clusters of genes is essential in revealing significant connections in gene regulatory networks. E-commerce applications, such as collaborative filtering, can also benefit from the new model, which captures not only the closeness of values of certain leading indicators but also the closeness of (purchasing, browsing, etc.) patterns exhibited by the customers. Our paper introduces an effective algorithm to detect such clusters, and we perform tests on several real and synthetic data sets to show its effectiveness.
Mining long sequential patterns in a noisy environment.
many applications including computational biology study, consumer behavior analysis, system performance analysis, etc. In a noisy environment, an observed sequence may not accurately reflect the underlying behavior. For example, in a protein sequence, the amino acid N is likely to mutate to D with little impact to the biological function of the protein. It would be desirable if the occurrence of D in the observation can be related to a possible mutation from N in an appropriate manner. Unfortunately, the support measure (i.e., the number of occurrences) of a pattern does not serve this purpose. In this paper, we introduce the concept of compatibility matrix as the means to provide a probabilistic connection from the observation to the underlying true value. A new metric match is also proposed to capture the &#034;real support&#034; of a pattern which would be expected if a noise-free environment is assumed. In addition, in the context we address, a pattern could be very long. The standard pruning technique developed for the market basket problem may not work efficiently. As a result, a novel algorithm that combines statistical sampling and a new technique (namely border collapsing) is devised to discover long patterns in a minimal number of scans of the sequence database with sufficiently high confidence. Empirical results demonstrate the robustness of the match model (with respect to the noise) and the efficiency of the probabilistic algorithm.
An Automated System for Web Portal Personalization.
This paper proposes a system for personalization  of web portals. A specific implementation  is discussed in reference to a web portal containing  a news feed service. Techniques are  proposed for effective categorization, management,  and personalization of news feeds obtained  from a live news wire service. The process  consists of two steps: first manual input is  required to build the domain knowledge which  could be site-specific; then the automated  component uses this domain knowledge in order  to perform the personalization, categorization  and presentation. Effective schemes for  advertising are proposed, where the targeting  is done using both the information about  the user and the content of the web page on  which the advertising icon appears. Automated  techniques for identifying sudden variations  in news patterns are described; these  may be used for supporting news-alerts. A description  of a version of this software for our  customer web site is provided.
Dynamic Refinement of Table Summarization or M%2DCommerce.

Optimal crawling strategies for web search engines.

Controlled replication for hash routing%2Dbased web caching.

The state of the art in locally distributed Web%2Dserver systems.

Controlled replication for hash routing%2Dbased web caching.

Finding Localized Associations in Market Basket Data.
In this paper, we discuss a technique for discovering localized associations in segments of the data using clustering. Often the aggregate behavior of a data set may be very di erent from localized segments. In such cases, it is desirable to design algorithms which are e ective in discovering localized associations, because they expose a customer pattern which is more speci c than the aggregate behavior. This information may bevery useful for target marketing. We present empirical results which show that the method is indeed able to nd a signi cantly larger number of associations than what can be discovered by analysis of the aggregate data.
Editorial.
calls &amp; calendarEDITORIAL
Redefining Clustering for High%2DDimensional Applications.
High dimensional data has always been a challenge for clustering algorithms because of the inherent sparsity of the points. Recent research results indicate that in high dimensional data, even the concept of proximity or clustering may not be meaningful. We discuss very general techniques for projected clustering which are able to construct clusters in arbitrarily aligned subspaces of lower dimensionality. The subspaces are specific to the clusters themselves. This definition is substantially more general and realistic than currently available techniques which limit the method to only projections from the original set of attributes. The generalized projected clustering technique may also be viewed as a way of trying to redefine clustering for high dimensional applications by searching for hidden subspaces with clusters which are created by inter-attribute correlations. We provide a new concept of using extended cluster feature vectors in order to make the algorithm scalable for very large databases. The running time and space requirements of the algorithm are adjustable, and are likely to tradeoff with better accuracy.
A Performance Study of Robust Load Sharing Strategies for Distributed Heterogeneous Web Server Systems.
Replication of information across multiple servers is becoming a common approach  to support popular Web sites. A distributed architecture with some mechanisms to  assign client requests to Web servers is more scalable than any centralized or mirrored  architecture. In this paper, we consider distributed systems in which the Authoritative  Domain Name Server (ADNS) of the Web site takes the request dispatcher role by  mapping the URL hostname into the IP address of a visible node that is, a Web  server or a Web cluster interface. This architecture can support local and geographical  distribution of the Web servers. However, the ADNS controls only a very small fraction  of the requests reaching the Web site because the address mapping is not requested for  each client access. Indeed, to reduce Internet trac, address resolution is cached at  various name servers for a time-to-live (TTL) period. This opens an entirely new set of  problems that traditional centralized schedulers of parallel/distributed systems do not  have to face. The heterogeneity assumption on Web node capacity, which is much more  likely in practice, increases the order of complexity of the request assignment problem,    c 2002 IEEE. IEEE Transactions on Knowledge and Data Engineering, Vol. 14, No. 2, pp. 398-414, March/April 2002. Personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution to servers or lists, or to reuse any copyrighted component of this work in other works, must be obtained from the IEEE. Contact: Manager, Copyrights and Permissions / IEEE Service Center / 445 Hoes Lane / P.O. Box 1331 / Piscataway, NJ 08855-1331, USA. Telephone: + Intl. 73...
Fast Algorithms for Online Generation of Profile Association Rules.

Introducing the New AEs.

Adaptive Piggybacking Schemes for Video%2DOn%2DDemand Systems.

Effective Nearest Neighbor Indexing with the Euclidean Metric.
The nearest neighbor search is an important operation widely-used in multimedia databases. In higher dimensions, most of previous methods for nearest neighbor search become inefficient and require to compute nearest neighbor distances to a large fraction of points in the space. In this paper, we present a new approach for processing nearest neighbor search with the Euclidean metric, which searches over only a small subset of the original space. This approach effectively approximates clusters by encapsulating them into geometrically regular shapes and also computes better upper and lower bounds of the distances from the query point to the clusters. For showing the effectiveness of the proposed approach, we perform extensive experiments. The results reveal that the proposed approach significantly outperforms the X-tree as well as the sequential scan.
On Effective Conceptual Indexing and Similarity Search in Text Data.
Similarity search in text has proven to be an interesting problem from the qualitative perspective because of inherent redundancies and ambiguities in textual descriptions. The methods used in search engines in order to retrieve documents most similar to user-defined sets of keywords are not applicable to targets which are medium to large size documents, because of even greater noise effects stemming from the presence of a large number of words unrelated to the overall topic in the document. The inverted representation is the dominant method for indexing text, but it is not as suitable for document-to-document similarity search, as for short user-queries. One way of improving the quality of similarity search is Latent Semantic Indexing (LSI), which maps the documents from the original set of words to a concept space. Unfortunately, LSI maps the data into a domain in which it is not possible to provide effective indexing techniques. In this paper, we investigate new ways of providing conceptual search among documents by creating a representation in terms of conceptual word-chains. This technique also allows effective indexing techniques so that similarity queries can be performed on large collections of documents by accessing a small amount of data. We demonstrate that our scheme outperforms standard textual similarity search on the inverted representation both in terms of quality and search efficiency.
SSDT A Scalable Subspace%2DSplitting Classifier for Biased Data.

Meta%2Dpatterns Revealing Hidden Periodic Patterns.
Discovery of periodic patterns in time series data has become an active research area with many applications. These patterns can be hierarchical in nature, where a higher level pattern may consist of repetitions of lower level patterns. Unfortunately, the presence of noise may prevent these higher level patterns from being recognized in the sense that two portions (of a data sequence) that support the same (high level) pattern may have different layouts of occurrences of basic symbols. There may not exist any common representation in terms of raw symbol combinations; and hence such (high level) pattern may not be expressed by any previous model (defined on raw symbols or symbol combinations) and would not be properly recognized by any existing method. In this paper, we propose a novel model, namely meta-pattern, to capture these high level patterns. As a more flexible model, the number of potential meta-patterns could be very large. A substantial difficulty lies on how to identify the proper pattern candidates. However, the well-known Apriori property is not able to provide sufficient pruning power. A new property, namely component location property, is identified and used to conduct the candidate generation so that an efficient  computation-based mining algorithm can be developed. Last but not least, we apply our algorithm to some real and synthetic sequences and some interesting patterns are discovered. 1 
Discovering unexpected information from your competitors%27 web sites.
Ever since the beginning of the Web, finding useful information from the Web has been an important problem. Existing approaches include keyword-based search, wrapper-based information extraction, Web query and user preferences. These approaches essentially find information that matches the user&#039;s explicit specifications. This paper argues that this is insufficient. There is another type of information that is also of great interest, i.e., unexpected information, which is unanticipated by the user. Finding unexpected information is useful in many applications. For example, it is useful for a company to find unexpected information about its competitors, e.g., unexpected services and products that its competitors offer. With this information, the company can learn from its competitors and/or design counter measures to improve its competitiveness. Since the number of pages of a typical commercial site is very large and there are also many relevant sites (competitors), it is very difficult for a human user to view each page to discover the unexpected information. Automated assistance is needed. In this paper, we propose a number of methods to help the user find various types of unexpected information from his/her competitors&#039; Web sites. Experiment results show that these techniques are very useful in practice and also efficient.  Keywords  Information interestingness, Web comparison, Web mining.  1. 
Infominer mining surprising periodic patterns.
lessoftheprobabilityofoccurrence.Amoresuitablemeathesensethateveryoccurrencecarriesthesameweightto- of5servers.Theworkloadoneachserverismeasured wardstheassessmentofthesignicanceofapatternregard by4ranks:low,relativelylow,relativelyhigh,andhigh. Thenthereare45=1024dierentevents,oneforeach surement,information,isintroducedtonaturallyvaluethe possiblecombinationofserverstates.Somepreliminary uousandmonotonicallydecreasingfunctionofitsprobabilitydegreeofsurpriseofeachoccurrenceofapatternasacontin- ofoccurrence.Thiswouldallowpatternswithvastlydierent occurrenceprobabilitiestobehandledseamlessly.Astheacoccuratamuchlowerfrequencythanotherstates,pat- examinationoftheclusterstatesovertimemightshow thatthestateuctuationcomplieswithsomeperiodic cumulateddegreeofsurpriseofallrepetitionsofapattern,thealldegreeofsurpriseofthepatternwithinadatasequence.conceptofinformationgainisproposedtomeasuretheovertemadministratorsiftheoccurrenceofsuchpattern(s)tern(s)involvingitmaybeofmoreintereststosomesys behavior.Althoughthehighworkloadonallserversmay Theboundedinformationgainpropertyisidentiedtotackle thepredicamentcausedbytheviolationofthedownwardclo- Earthquake.EarthquakesoccurveryofteninCalifornia. surepropertybytheinformationgainmeasureandinturn demonstratetheeciencyandtheusefulnessoftheproposed providesanecientsolutiontothisproblem.Empiricaltests maybeinterestedinknowingwhetherthereexistsany contradictsthepriorexpectation. inherentseismicperiodsothatpredictioncanbemade. Itcanbeclassiedbyitsmagnitudeandtype.Scientist model.
Outlier Detection for High Dimensional Data.
The outlier detection problem has important applications in the eld of fraud detection, netw ork robustness analysis, and intrusion detection. Most suc h applications are high dimensional domains in whic hthe data can con tain hundreds of dimensions. Many recen t algorithms use concepts of pro ximity in order to nd outliers based on their relationship to the rest of the data. Ho w ever, in high dimensional space, the data is sparse and the notion of proximity fails to retain its meaningfulness. In fact, the sparsity of high dimensional data implies that every point is an almost equally good outlier from the perspective ofproximity-based de nitions. Consequently, for high dimensional data, the notion of nding meaningful outliers becomes substantially more complex and non-obvious. In this paper, w e discuss new techniques for outlier detection whic h nd the outliers by studying the behavior of projections from the data set. 1.
Segment%2Dbased proxy caching of multimedia streams.
As streaming video and audio over the Internet becomes popular, proper proxy caching of large multimedia objects has become increasingly important. For a large media object, such as a 2-hour video, treating the whole video as a single web object for caching is not appropriate. In this paper, we present and evaluate a segment-based buffer management approach to proxy caching of large media streams. Blocks of a media stream received by a proxy server are grouped into variable-sized segments. The cache admission and replacement policies then attach different caching values to different segments, taking into account the segment distance from the start of the media. These caching policies give preferential treatments to the beginning segments. As such, users can quickly play back the media objects without much delay. Event-driven simulations are conducted to evaluate this segment-based proxy caching approach. The results show that (1) segment-based caching is effective not only in increasing byte-hit ratio (or reducing total traffic) but also in lowering the number of requests that require delayed starts; (2) segment-based caching is especially advantageous when the cache size is limited, when the set of hot media objects changes over time, when the media file size is large, and when many users may stop playing the media after only a few initial blocks.
Intelligent crawling on the World Wide Web with arbitrary predicates.
The enormous growth of the world wide web in recent years has made it important to perform resource discovery efficiently. Consequently, several new ideas have been proposed in recent years; among them a key technique is focused crawling which is able to crawl particular topical portions of the world wide web quickly without having to explore all web pages. In this paper, we propose the novel concept of intelligent crawling which actually learns characteristics of the linkage structure of the world wide web while performing the crawling. Specifically, the intelligent crawler uses the inlinking web page content, candidate URL structure, or other behaviors of the inlinking web pages or siblings in order to estimate the probability that a candidate is useful for a given crawl. This is a much more general framework than the focused crawling technique which is based on a pre-defined understanding of the topical structure of the web. The techniques discussed in this paper are applicable for crawling web pages which satisfy arbitrary user-defined predicates such as topical queries, keyword queries or any combinations of the above. Unlike focused crawling, it is not necessary to provide representative topical examples, since the crawler can learn its way into the appropriate topic. We refer to this technique as intelligent crawling because of its adaptive nature in adjusting to the web page linkage structure. The learning crawler is capable of reusing the knowledge gained in a given crawl in order to provide more efficient crawling for closely related predicates.
On the design of a learning crawler for topical resource discovery.

On balancing the load in a clustered web farm.

Thrashing control and avoidance for concurrent mergesorts using parallel prefetching.

The Maximum Factor Queue Length Batching Scheme for Video%2Don%2DDemand Systems.

Editorial.
calls &amp; calendarEDITORIAL
Editorial Introducing the New AEs.

A New Approach to Online Generation of Association Rules.

Scheduling Algorithms for the Broadcast Delivery of Digital Products.

Mining Associations with the Collective Strength Approach.

Load balancing for clustered web farms.

Clustering Through Decision Tree Construction.
this paper, we propose a novel clustering technique, which is based on a supervised learning technique called decision tree construction. The new technique is able to overcome many of these shortcomings. The key idea is to use a decision tree to partition the data space into cluster and empty (sparse) regions at different levels of details. The technique is able to find &#034;natural&#034; clusters in large high dimensional spaces efficiently. It is suitable for clustering in the full dimensional space as well as in subspaces. It also provides comprehensible descriptions of clusters. Experiment results on both synthetic data and real-life data show that the technique is effective and also scales well for large high dimensional datasets.
Collaborative Proxy System for Distributed Web Content Transcoding.

TabSum A Flexible and Dynamic Table Summarization Approach.


The Intelligent Recommendation Analyzer.


The IGrid index reversing the dimensionality curse for similarity indexing in high dimensional space.
The similarity searc h and indexing problem is w ell kno wn to be a di cult one for high dimensional applications. Most indexing structures show a rapid degradation with increasing dimensionality whic hleads to an access of the en tire database for each query. F urthermore, recen t research results sho w that in high dimensional space, even the concept of similarity may not be very meaningful. In this paper, w e propose theIGrid-index; a method for similarity indexing which uses a distance function whose meaningfulness is retained with increasing dimensionality. In addition, this technique shows performance which is unique to all known index structures; the percentage of data accessed is inversely proportional to the overall data dimensionality. Th us, this technique relies on the dimensionality to be high in order to pro vide performance e cient similarity results. The IGridindex can also support a special kind of query whic hw e refer to as projected range queries; a query whic his increasingly relevan tfor very high dimensional data mining applications.
Efficient mining of weighted association rules %28WAR%29.
In this paper, we extend the tradition association rule problem by allowing a weight to be associated with each item in a transaction, to reflect interest/intensity of the item within the transaction. This provides us in turn with an opportunity to associate a weight parameter with each item in the resulting association rule. We call it weighted association rule (WAR). WAR not only improves the confidence of the rules, but also provides a mechanism to do more effective target marketing by identifying or segmenting customers based on their potential degree of loyalty or volume of purchases. Our approach mines WARs by first ignoring the weight and finding the frequent itemsets (via a traditional frequent itemset discovery algorithm), and is followed by introducing the weight during the rule generation. It is shown by experimental results that our approach not only results in shorter average execution times, but also produces higher quality results than the generalization of previous known methods on quantitative association rules.
Mining asynchronous periodic patterns in time series data.
Periodicy detection in time series data is a challenging problem of great importance in many applications.
Targeting the right students using data mining.
The education domain offers a fertile ground for many interesting and challenging data mining applications. These applications can help both educators and students, and improve the quality of education. In this paper, we present a real-life application for the Gifted Education Programme (GEP) of the Ministry of Education (MOE) in Singapore. The application involves many data mining tasks. This paper focuses only on one task, namely, selecting students for remedial classes. Traditionally, a cut-off mark for each subject is used to select the weak students. That is, those students whose scores in a subject fall below the cut-off mark for the subject are advised to take further classes in the subject. In this paper, we show that this traditional method requires too many students to take part in the remedial classes. This not only increases the teaching load of the teachers, but also gives unnecessary burdens to students, which is particularly undesirable in our case because the GEP students are generally taking more subjects than non-GEP students, and the GEP students are encouraged to have more time to explore advanced topics. With the help of data mining, we are able to select the targeted students much more precisely.
Geographic Load Balancing for Scalable Distributed Web Systems.
Users of highly popular Web sites may experience long delays when accessing information. Upgrading content site infrastructure from a single node to a locally distributed Web cluster composed by multiple server nodes provides a limited relief, because the cluster wide-area connectivity may become the bottleneck. A better solution is to distribute Web clusters over the Internet by placing content nodes in strategic locations. A geographically distributed architecture where the Domain Name System (DNS) servers evaluate network proximity and users are served from the closest cluster reduces network impact on response time. On the other hand, serving closest requests only may cause unbalanced servers and may increase system impact on response time. To achieve a scalable Web system, we propose to integrate DNS proximity scheduling with an HTTP request redirection mechanism that any Web server can activate. We demonstrate through simulation experiments that this further dispatching mechanism augments the percentage of requests with guaranteed response time, thereby enhancing the Quality of Service of geographically distributed Web sites. However, HTTP request redirection should be used selectively because the additional round-trip increases network impact on latency time experienced by users. As a further contribution, this paper proposes and compares various mechanisms to limit reassignments with no negative consequences on load balancing. 1.
Finding Generalized Projected Clusters In High Dimensional Spaces.
High dimensional data has always been a challenge for clustering algorithms because of the inherent sparsity of the points. Recent research results indicate that in high dimensional data, even the concept of proximity or clustering may not be meaningful. We discuss very general techniques for projected clustering which are able to construct clusters in arbitrarily aligned subspaces of lower dimensionality. The subspaces are specific to the clusters themselves. This definition is substantially more general and realistic than currently available techniques which limit the method to only projections from the original set of attributes. The generalized projected clustering technique may also be viewed as a way of trying to redefine clustering for high dimensional applications by searching for hidden subspaces with clusters which are created by inter-attribute correlations. We provide a new concept of using extended cluster feature vectors in order to make the algorithm scalable for very large databases. The running time and space requirements of the algorithm are adjustable, and are likely to tradeoff with better accuracy.
Latency%2Dsensitive hashing for collaborative Web caching.

Workfile Disk Management for Concurrent Mergesorts in a Multiprocessor Database System.

Data Mining Techniques for Personalization.
This paper discusses an overview of data mining techniques for personalization. It discusses some of the standard techniques which are used in order to adapt and increase the ability of the system to tailor itself to specific user behavior. We discuss several such techniques such as collaborative filtering, content based methods, and content based collaborative filtering methods. We examine the specific applicability of these techniques to various scenarios and the broad advantages of each in specific situations. 1
Mining Patterns in Long Sequential Data with Noise.

Report on Second International Workshop on Advanced Issues of E%2DCommerce and Web%2Dbased Information Systems.

Local Replication for Proxy Web Caches with Hash Routing.

Data Mining and Personalization Technologies.

Redirection Algorithms for Load Sharing in Distributed Web%2Dserver Systems.
is necessary to support high request rates to popular Web sites. A clustered Web-server organization is preferable to multiple independent mirrored-servers because it maintains a single interface to the users and has the potential to be more scalable, fault-tolerant and better load balanced. In this paper we propose a Web cluster architecture in which the Domain Name System server (DNS), that dispatches the user requests among the servers through the URL-name to IP-address mapping mechanism, is integrated with a redirection request mechanism based on the HTTP protocol. This should alleviate the side effect of caching the IP-address mapping at intermediate name servers. We compare many alternative mechanisms, including synchronous vs asynchronous activation, and centralized vs distributed decision on redirection. Moreover, we analyze reassignment of entire domains or individual client requests, different types of status information, and different server selection policies for redirecting requests. Our results show that the combination of centralized and distributed dispatching policies allows the Web-server cluster to handle the high load skews in the WWW environment.
Load Balancing and Hot Spot Relief for Hash Routing among a Collection of Proxy Caches.

Horting Hatches an Egg A New Graph%2DTheoretic Approach to Collaborative Filtering.
This paper introduces a new and novel approach to ratingbased collaborative filtering. The new technique is most appropriate for e-commerce merchants offering one or more groups of relatively homogeneous items such as compact disks, videos, books, software and the like. In contrast with other known collaborative filtering techniques, the new algorithm is graph-theoretic, based on the twin new concepts of horting and predictability. As is demonstrated in this paper, the technique is fast, scalable, accurate, and requires only a modest learning curve. It makes use of a hierarchical classification scheme in order to introduce context into the rating process, and uses so-called creative links in order to find surprising and atypical items to recommend, perhaps even items which cross the group boundaries. The new technique is one of the key engines of the Intelligent Recommendation Algorithm (IRA) project, now being developed at IBM Research. In addition to several other recommendation engines, IRA contains a situation analyzer to determine the most appropriate mix of engines for a particular e-commerce merchant, as well as an engine for optimizing the placement of advertisements.
Adaptive Query Processing for Time%2DSeries Data.
ywh @ us.ibm.com Traditional query process for time-series data transforms data from the time domain into the frequency domain. It is less controllable by the end users, therefore isn’t well suited for queries that find patterns with many dynamically specified user constraints. For these queries we present a method to search time-series data which first transforms time sequences into symbol strings using change ratio between contiguous data points in time series. Next, a suffix tree is built to index all suffixes of the symbol strings. The focus of this paper is to demonstrate how this method can adapt to the processing of the dynamically constrained time-series queries.
On the Merits of Building Categorization Systems by Supervised Clustering.
This paper investigates the use of supervised clustering in order to create sets of categories for classification of documents. We use information from a pre-existing taxonomy in order to supervise the creation of a set of related clusters, though with some freedom in defining and creating the classes. We show that the advantage of using supervised clustering is that it is possible to have some control over the range of subjects that one would like the categorization system to address, but with a precise mathematical definition of each category. We then categorize documents using this a priori knowledge of the definition of each category. We also discuss a new technique to help the classifier distinguish better among closely related clusters. Finally, we show empirically that this categorization system utilizing a machine-derived taxonomy performs as well as a manual categorization process, but at a far lower cost. 1
Optimizing Profits in the Broadcast Delivery of Multimedia Products.

Data Mining Techniques for Associations%2C Clustering and Classification.

Replication Issues on Proxy Cache Array.

On Text Mining Techniques for Personalization.

A New Method for Similarity Indexing of Market Basket Data.
In recent years, many data mining methods have been proposed for finding useful and structured information from market basket data. The association rule model was recently proposed in order to discover useful patterns and dependencies in such data. This paper discusses a method for indexing market basket data efficiently for similarity search. The technique is likely to be very useful in applications which utilize the similarity in customer buying behavior in order to make peer recommendations. We propose an index called the signature table, which is very flexible in supporting a wide range of similarity functions. The construction of the index structure is independent of the similarity function, which can be specified at query time. The resulting similarity search algorithm shows excellent scalability with increasing memory availability and database size.
Fast Algorithms for Projected Clustering.
� Researches of text clustering � Possible applications of text clustering � Existing text clustering system
Review %2D Mining Association Rules between Sets of Items in Large Databases.

Dynamic Load Balancing on Web%2DServer Systems.

Caching on the World Wide Web.
The continued increase in demand for information services on the Internet is showing signs of strain. While the Internet is a highly distributed system, individual data objects most often have only a single source. Host computers and network links can easily become overloaded when a large number of users access very popular data. Proxy-caching is currently a popular way to reduce network bandwidth, server load and to improve response time to the user. The original caching proxy, from CERN, is probably still the most widely used. This paper describes software developed by the author that investigates some alternative techniques for caching World-Wide Web objects. This software complements traditional proxycaching by allowing servers to explicitly grant or deny permission to cache an object, and with support for server-initiated callback invalidation of changed objects. 1 Introduction  Statistics collected on the NSFNET backbone were indicating that World-Wide Web traffic would exceed th...
Scan A Hierarchical Algorithm for Similarity Search in Databases Consisting of Long Sequences.

Using Unbalanced Trees for Indexing Multidimensional Objects.

Run Placement Policies for Concurrent Mergesorts Using Parallel Prefetching.

Design and Analysis of Permutation%2DBased Pyramid Broadcasting.

DNS Dispatching Algorithms with State Estimators for Scalable Web%2DServer Clusters.
Replication of information across a server cluster provides a promising way to support popular Web sites. However, a Web-server cluster requires some mechanism for the scheduling of requests to the most available server. One common approach is to use the local Domain Name Server (DNS) as a centralized dispatcher. The main problem is that WWW address caching mechanisms (although reducing network trac) only let this DNS dispatcher control a very small fraction of the requests reaching the Web-server cluster. The nonuniformity of the load from dierent client domains, and the high variability of real Web workload introduce additional degrees of complexity to the load balancing issue. These characteristics make existing scheduling algorithms for traditional distributed systems not applicable to control the load of Web-server clusters and motivate the research on entirely new DNS policies that require some system state information. We analyze various DNS dispatching policies under realistic situations where state information needs to be estimated with low computation and communication overhead so as to be applicable to a Web cluster architecture. In a model of realistic scenarios for the Web cluster, a large set of simulation experiments shows that, by incorporating the proposed state estimators into the dispatching policies, the eectiveness of the DNS scheduling algorithms can improve substantially, in particular if compared to the results of DNS algorithms not using adequate state information.
MALM A Framework for Mining Sequence Database at Multiple Abstraction Levels.

MALM A Framework for Mining Sequence Database at Multiple Abstraction Levels.

Online Algorithms for Finding Profile Association Rules.

Efficient State Estimators for Load Control Policies in Scalable Web Server Clusters.
Replication of information across a server cluster provides a promising way to support popular Web sites. However, a Web server cluster requires some mechanism for directing requests to the best server. One common approach is to use the Domain Name Server (DNS) as a centralized scheduler. However, address caching mechanisms and the non-uniformity of the load from different client domains complicate the load balancing issue and make existing scheduling algorithms for traditional distributed systems not applicable to Web server clusters. In this paper, we consider the theoretical DNS policies that require some system state information. We extend them to realistic situations where state information needs to be estimated with low computation and communication overhead. We show that, by incorporating these estimators into the DNS policies, load balancing improves substantially, even if the DNS control is limited to a small portion of client requests. 1.
Range%2DBased Bitmap Indexing for High Cardinality Attributes with Skew.

Dynamic Load Balancing in Geographically Distributed Heterogeneous Web Servers.
With ever increasing Web traffic, a distributed multi-server Web site can provide scalability and flexibility to cope with growing client demands. Load balancing algorithms to spread the requests across multiple Web servers are crucial to achieve the scalability. Various domain name server (DNS) based schedulers have been proposed in the literature, mainly for multiple homogeneous servers. The presence of heterogeneous Web servers not only increases the complexity of the DNS scheduling problem, but also makes previously proposed algorithms for homogeneous distributed systems not directly applicable. This leads us to propose new policies, called adaptive TTL algorithms, that take into account of both the uneven distribution of client request rates and heterogeneity of Web servers to adaptively set the time-to-live (TTL) value for each address mapping request. Extensive simulation results show that these strategies are robust and effective in balancing load among geographically distribut...
A Bandwidth%2DSensitive Update Scheduling Method for Internet Push.

Online Generation of Association Rules.
We have a large database consisting of sales transactions. We investigate the problem of online mining of association rules in this large database. We show how to preprocess the data effectively in order to make it suitable for repeated online queries. The preprocessing algorithm takes into account the storage space available. We store the preprocessed data in such a way that online processing may be done by applying a graph theoretic search algorithm whose complexity is proportional to the size of the output. This results in an online algorithm which is practically instantaneous in terms of response time. The algorithm also supports techniques for quickly discovering association rules from large itemsets. The algorithm is capable of finding rules with specific items in the antecedent or consequent. These association rules are presented in a compact form, eliminating redundancy. We believe that the elimination of redundancy in online generation of association rules from large itemsets is interesting in its own right.
Online Generation of Profile Association Rules.

A New Framework For Itemset Generation.
The problem of finding association rules in a large database of sales transactions has been widely studied in the literature. We discuss some of the weaknesses of the large itemset method for association rule generation. A different method for evaluating and finding itemsets referred to as strongly collective itemsets is proposed. The concepts of &#034;support&#034; of an itemset and correlation of the items within an itemset are related, though not quite the same. This criterion stresses the importance of the actual correlation of the items with one another rather than the absolute support. Previously proposed methods to provide correlated itemsets are not necessarily applicable to very large databases. We provide an algorithm which provides very good computational efficiency, while maintaining statistical robustness. The fact that this algorithm relies on relative measures rather than absolute measures such as support also implies that the method can be applied to find association rules in datasets in which items may appear in a sizeable percentage of the transactions (dense datasets), datasets in which the items have varying density, or even negative association rules.
A Framework for the Optimizing of WWW Advertising.

Performance Study of a Collaborative Method for Hierarchical Caching in Proxy Servers.

Energy%2DEfficient Mobile Cache Invalidation.
Caching data in a wireless mobile computer can significantly reduce the bandwidth requirement. However, due to battery power limitation, a wireless mobile computer may often be forced to operate in a doze or even totally disconnected mode. As a result, the mobile computer may miss some cache invalidation reports. In this paper, we present an energy-efficient cache invalidation method for a wireless mobile computer. The new cache invalidation scheme is called grouping with cold update-set retention (GCORE). Upon waking up, a mobile computer checks its cache validity with the server. To reduce the bandwidth requirement for validity-checking, data objects are partitioned into groups. However, instead of simply invalidating a group if any of the objects in the group has been updated, GCORE retains the cold update set of objects in a group if possible. We present an efficient implementation of GCORE and conduct simulations to evaluate its caching effectiveness. The results show that GCORE can subs...
SpeedTracer A Web Usage Mining and Analysis Tool.
usage mining and analysis tool SpeedTracer, a World Wide Web usage mining and analysis tool, was developed to understand user surfing behavior by exploring the Web server log files with data mining techniques. As the popularity of the Web has exploded, there is a strong desire to understand user surfing behavior. However, it is difficult to perform useroriented data mining and analysis directly on the server log files because they tend to be ambiguous and incomplete. With innovative algorithms, SpeedTracer first identifies user sessions by reconstructing user traversal paths. It does not require “cookies ” or user registration for session identification. User privacy is protected. Once user sessions are identified, data mining algorithms are then applied to discover the most common traversal paths and groups of pages frequently visited together. Important user browsing patterns are manifested through the frequent traversal paths and page groups, helping the understanding of user surfing behavior. Three types of reports are prepared: user-based reports, path-based reports and group-based reports. In this paper, we describe the design of SpeedTracer and demonstrate some of its features with a few sample reports. opularity of the World Wide Web (WWW) on P the Internet has exploded recently. Many organizations have invested a tremendous amount of capital to operate sites on the Web. These Web sites provide communications and services to their employees, customers, and suppliers. With money invested in these sites, there is a strong desire to understand the effectiveness of such investments and to find ways to realize the potential opportunities
Mining Large Itemsets for Association Rules.
This paper provides a survey of the itemset method for association rule generation. The paper discusses past research on the topic and also studies the relevance and importance of the itemset method in generating association rules. We discuss a number of variations of the association rule problem which have been proposed in the literature and their practical applications. Some inherent weaknesses of the large itemset method for association rule generation have been explored. We also discuss some other formulations of associations which can be viable alternatives to the traditional association rule generation method. 1 Introduction  Association rules find the relationships between the different items in a database of sales transactions. Such rules track the buying patterns in consumer behavior eg. finding how the presence of one item in the transaction affects the presence of another and so forth. The problem of association rule generation has recently gained considerable prominence in ...
Analysis of Task Assignment Policies in Scalable Distributed Web%2DServer Systems.
A distributed multi-server Web site can provide the scalability necessary to keep up with growing client demand at popular sites. Load balancing of these distributed Web-server systems, consisting of multiple Web servers for document retrieval and a Domain name server (DNS) for address resolution, opens interesting new problems. In this paper, we investigate the effects of using a more active DNS which, as an atypical centralized scheduler, applies some scheduling strategy in routing the requests to the most suitable Web server. Unlike traditional parallel/distributed systems in which a centralized scheduler has full control of the system, the DNS controls only a very small fraction of the requests reaching the multi-server Web site. This peculiarity, especially in the presence of highly skewed load, makes it very difficult to achieve acceptable load balancing and avoid overloading some Web server. This paper adapts traditional scheduling algorithms to the DNS, proposes new policies, a...
Efficient Data Mining for Path Traversal Patterns.
Abstract—In this paper, we explore a new data mining capability that involves mining path traversal patterns in a distributed information-providing environment where documents or objects are linked together to facilitate interactive access. Our solution procedure consists of two steps. First, we derive an algorithm to convert the original sequence of log data into a set of maximal forward references. By doing so, we can filter out the effect of some backward references, which are mainly made for ease of traveling and concentrate on mining meaningful user access sequences. Second, we derive algorithms to determine the frequent traversal patterns¦i.e., large reference sequences¦from the maximal forward references obtained. Two algorithms are devised for determining large reference sequences; one is based on some hashing and pruning techniques, and the other is further improved with the option of determining large reference sequences in batch so as to reduce the number of database scans required. Performance of these two methods is comparatively analyzed. It is shown that the option of selective scan is very advantageous and can lead to prominent performance improvement. Sensitivity analysis on various parameters is conducted. Index Terms—Data mining, traversal patterns, distributed information system, World Wide Web, performance analysis.
Analysis of Task Assignment Policies in Scalable Distributed Web%2DServer Systems.
A distributed multi-server Web site can provide the scalability necessary to keep up with growing client demand at popular sites. Load balancing of these distributed Web-server systems, consisting of multiple Web servers for document retrieval and a Domain name server (DNS) for address resolution, opens interesting new problems. In this paper, we investigate the effects of using a more active DNS which, as an atypical centralized scheduler, applies some scheduling strategy in routing the requests to the most suitable Web server. Unlike traditional parallel/distributed systems in which a centralized scheduler has full control of the system, the DNS controls only a very small fraction of the requests reaching the multi-server Web site. This peculiarity, especially in the presence of highly skewed load, makes it very difficult to achieve acceptable load balancing and avoid overloading some Web server. This paper adapts traditional scheduling algorithms to the DNS, proposes new policies, a...
Exploring Wait Tolerance in Effective Batching for Video%2Don%2DDemand Scheduling.
In a Video-on-demand (VOD) computer system, batching requests for the same video to share a common data stream can lead to significant improvement in throughput. Using the  wait tolerance characteristic that is commonly observed in viewers behavior, we introduce a new paradigm for scheduling in VOD systems. We propose and analyze two classes of scheduling schemes: the Max Batch and Min Idle schemes, that provide two alternative ways for using a given stream capacity for effective batching. In making a video selection, the proposed schemes take into consideration the next stream completion time as well as the viewer wait tolerance. We compared the proposed schemes with the two previously studied schemes: (1) first-come-firstserved (FCFS) that schedules the video with the longest waiting request and (2) the maximum queue length (MQL) scheme that selects the video with the maximum number of waiting requests. We show through simulations that the proposed schemes outperform substantially FC...
Increasing Multimedia System Throughput with Consumption%2Dbased Buffer Management.

On Analytic Modeling of Multimedia Batching Schemes.

Smart SMART Bounds for Weighted Response Time Scheduling.
Consider a system of independent tasks to be scheduled without preemption on a parallel computer. For each task the number of processors required, the execution time, and a weight are known. The problem is to nd a schedule with minimum weighted average response time. We present an algorithm called SMART for this problem that produces solutions that are within a factor of 10.45 of optimal. To our knowledge this is the rst polynomial-time algorithm for the minimum weighted average response time problem that achieves a constant bound. In addition, for the unweighted case (that is, where all the weights are unity) we describe a variant of SMART that produces solutions that are within a factor of 8 of optimal, improving upon the best known bound of 32 for this special case. 1
Reminiscences on Influential Papers.

Mining Association Rules with Adjustable Accuracy.
In this paper, we devise efficient algorithms for mining association rules with adjustable accuracy. It is noted that several applications require mining the transaction data to capture the customer behavior frequently. In those applications, the efficiency of data mining could be a more important factor than the requirement for complete accuracy of the mining results. Allowing imprecise results can significantly improve the data mining efficiency. In this paper, two methods for mining association rules with adjustable accuracy are developed. By dealing with the concept of sampling, both methods obtain some essential knowledge from a sampled subset first, and in light of that knowledge, perform efficient association rule mining on the entire database. A technique of relaxing the support factor based on the sampling size is devised to achieve the desired level of accuracy. These two methods differ from each other in their ways of utilizing the sampled data. Performance of these two meth...
On Disk Caching of Web Objects in Proxy Servers.

On Disk Caching of Web Objects in Proxy Servers.


Indexed Sequential Data Broadcasting in Wireless Mobile Computing.
Energy saving is one of the most important issues in wireless mobile computing. Among others, one viable approach to achieving energy saving is to use an indexed data organization to broadcast data over wireless channels to mobile units. In this paper, we explore the issue of indexing data with skewed access for sequential broadcasting in wireless mobile computing. We propose methods to build index trees based on access frequencies of data records. To minimize the average cost of index probes, we consider two cases: one for fixed index fanouts and the other for variant index fanouts, and devise algorithms to construct index trees for both cases. We show that the cost of index probes can be minimized not only by employing an imbalanced index tree that is designed in accordance with data access skew, but also by exploiting variant fanouts for index nodes. 1 Introduction  Mobile computing, referring to the activity of using personal digital assistances, such as palmtops and notebook compu...
Scheduling Algorithms for Distributed Web Servers.


Cluster Architectures and S%2F390 Parallel Sysplex Scalability.

Divergence Control Algorithms for Epsilon Serializability.
This paper presents distributed divergence control algorithms for epsilon serializability for both homogeneous and heterogeneous distributed databases. Epsilon serializability allows for more concurrency by permitting non-serializable interleavings of database operations among epsilon transactions. We first present a strict 2-phase locking divergence control algorithm and an optimistic divergence control algorithm for a homogeneous distributed database system, where the local orderings of all the sub-transactions of a distributed epsilon transaction are the same. In such an environment, the total inconsistency of a distributed epsilon transaction is simply the sum of those of all its sub-transactions. We then describe a divergence control algorithm for a heterogeneous distributed database system, where the local orderings of all the sub-transactions of a distributed epsilon transaction may not be the same and the total inconsistency of a distributed epsilon transaction may be greater t...
Optimal Design of Multiple Hash Tables for Concurrency Control.

Using a Hash%2DBased Method with Transaction Trimming for Mining Association Rules.

Recovery Analysis of Data Sharing Systems under Deferred Dirty Page Propagation Policies.

Parallel Execution of Hash Joins in Parallel Databases.
In this paper we explore two important issues, processor allocation and the use of hash filters,  to improve the parallel execution of hash joins. To exploit the opportunity of pipelining for hash  join execution, a scheme to transform a bushy execution tree to an allocation tree is first devised.  In an allocation tree, each node denotes a pipeline. Then, using the concept of synchronous  execution time, processors are allocated to the nodes in the allocation tree in such a way that  inner relations in a pipeline can be made available approximately the same time. Also, the  approach of hash filtering is investigated to further improve the parallel execution of hash joins.  Extensive performance studies are conducted via simulation to demonstrate the importance of  processor allocation and to evaluate various schemes using hash filters. It is experimentally  shown that processor allocation is in general the dominant factor to performance, and the effect  of hash filtering becomes more ...
Disk Load Balancing for Video%2DOn%2DDemand Systems.
For a video-on-demand computer system we propose a scheme which balances the load on the disks, thereby helping to solve a performance problem crucial to achieving maximal video throughput. Our load balancing scheme consists of two components. The static component determines good assignments of videos to groups of striped disks. The dynamic component uses these assignments, and features a &#034;DASD dancing&#034; algorithm which performs realtime disk scheduling in an effective manner. Our scheme works synergistically with disk striping. We examine the performance of the proposed algorithm via simulation experiments. 1 Introduction  Consider a video-on-demand (VOD) computer system consisting of a central processor and a collection of shared disks, sometimes known as direct access storage devices  (DASDs). VOD computer systems must be able to &#034;play&#034; multiple streams of many different videos simultaneously, based on customer demand. Most videos will be stored most cost effectively on disk. (A few ...
Using Rotational Mirrored Declustering for Replica Placement in a Disk%2DArray%2DBased Video Server.
In a video-on-demand (VOD) environment, disk-arrays are often used to support the disk bandwidth requirement. This can pose serious problems on available disk bandwidth upon disk failure. In this paper, we explore the approach of replicating frequently accessed movies to provide high data bandwidth and fault-tolerance required in a disk-array-based video server. An isochronous continuous video stream imposes different requirements from a random access pattern on databases or files. Explicitly, we propose a new replica placement method, called  rotational mirrored declustering (RMD), to support high data availability for disk arrays in a VOD environment. In essence, RMD is similar to the conventional mirrored declustering in that replicas are stored in different disk arrays, however different from the latter in that the replica placements in different disk arrays under RMD are properly rotated. Combining the merits of prior chained and mirrored declustering methods, RMD is particularly ...
Adaptive TTL Schemes for Load Balancing of Distributed Web Servers.

On Applying Hash Filters to Improving the Execution of Multi%2DJoin Queries.
.&lt;F3.733e+05&gt; In this paper, we explore an approach of interleaving a bushy execution tree with hash filters to improve the execution of multi-join queries. Similar to semi-joins in distributed query processing, hash filters can be applied to eliminate non-matching tuples from joining relations before the execution of a join, thus reducing the join cost. Note that hash filters built in different execution stages of a bushy tree can have different costs and effects. The effect of hash filters is evaluated first. Then, an efficient scheme to determine an effective sequence of hash filters for a bushy execution tree is developed, where hash filters are built and applied based on the join sequence specified in the bushy tree so that not only is the reduction effect optimized but also the cost associated is minimized. Various schemes using hash filters are implemented and evaluated via simulation. It is experimentally shown that the application of hash filters is in general a very powerful ...
Efficient Data Mining for Path Traversal Patterns in Distributed Systems.

Energy%2DEfficient Caching for Wireless Mobile Computing.

HierarchyScan A Hierarchical Similarity Search Algorithm for Databases of Long Sequences.

A Permutation%2DBased Pyramid Broadcasting Scheme for Video%2Don%2DDemand Systems.

Consumption%2DBased Buffer Management for Maximizing System Throughput of a Multimedia System.

On Optimal Batching Policies for Video%2Don%2DDemand Storage Servers.

On Optimal Piggyback Merging Policies for Video%2Don%2DDemand Systems.
Abstract A critical issue in the performance of a video-on-demand system is the 1/0 bandwidth re-quired in order to satisfy client requests. A number of techniques have been proposed in order to reduce these bandwidth requirements. In this paper we concentrate on one such technique, known as adaptive piggyback-ing. We develop and analyze piggyback merging poli-cies which are optimal over large classes of reasonable methods. 1
Modeling and Analysis of Concurrency Control Schemes.

Analytic Modeling of Clustered RAID with Mapping Based on Nearly Random Permutation.

On Coupling Multiple Systems With A Global Buffer.
In this paper, we conduct a performance study of coupling multiple systems with a global buffer, and present several results obtained from a multiple-system simulator. This simulator has been run against three workloads, and the coupled system behavior with these three different inputs is studied. Several statistics, including those on local and global buffer hits, page writes to the global buffer, cross-invalidations and castouts, and their relationship to the degree of data skew is explored. Moreover, in addition to the update-caching approach, a design alternative for the use of a global buffer, namely read-caching, is explored. In read-caching, not only updated pages but also pages read by each node are kept in the global buffer, thereby facilitating other nodes&#039; access to the same pages at the cost of a higher global buffer usage. Also investigated is the case of no-caching, i.e., without using a global buffer. Several simulation results are presented and analyzed. Index Terms: Da...
Optimization of Parallel Execution for Multi%2DJoin Queries.
In this paper, we study the subject of exploiting inter-operator parallelism to optimize the execution of multi-join queries. Specifically, we focus on two major issues: (i) scheduling the execution sequence of multiple joins within a query, and (ii) determining the number of processors to be allocated for the execution of each join operation obtained in (i). For the first issue, we propose and evaluate by simulation several methods to determine the general join sequences, or bushy trees. Despite their simplicity, the heuristics proposed can lead to the general join sequences which significantly outperform the optimal sequential join sequence. The quality of the join sequences obtained by the proposed heuristics is shown to be fairly close to that of the optimal one. For the second issue, it is shown that the processor allocation for exploiting inter-operator parallelism is subject to more constraints, such as execution dependency and system fragmentation, than those in the study of in...
Data Mining An Overview from a Database Perspective.

Performance Analysis of Dynamic Finite Versioning Schemes Storage Cost vs. Obsolescence.

Efficient LRU%2DBased Buffering in a LAN Remote Caching Architecture.

On General Results for All%2Dto%2DAll Broadcast.
All-to-all broadcast refers to the process by which every node broadcasts its certain piece of information to all other nodes in the system. In this paper, we develop all-to-all broadcast schemes by dealing with two classes of schemes. A prior scheme based on generation of minimal complete sets is first described, and then a new scheme based on propagation of experts is developed. The former always completes the broadcasting in the minimal number of steps and the latter is designed to minimize the number of messages. Performance of these two classes of schemes is comparatively analyzed. The all-to-all broadcast scheme desired can be derived by combining the advantages of these two classes of schemes.  Index Terms: All-to-all broadcast, message passing, NODUP, expert propagation, communication steps.  1 Introduction Instead of using a shared memory and a global clock, the synchronization and communication between the processing nodes in a distributed system can be done via message pass...
Using Content%2DBased Search to Download Digital Video into a Client Station.

Proceedings of the Eleventh International Conference on Data Engineering

Using Rotational Mirrored Declustering for Replica Placement in a Disk%2DArray%2DBased Video Server.
In a video-on-demand (VOD) environment, disk-arrays are often used to support the disk bandwidth requirement. This can pose serious problems on available disk bandwidth upon disk failure. In this paper, we explore the approach of replicating frequently accessed movies to provide high data bandwidth and fault-tolerance required in a disk-array-based video server. An isochronous continuous video stream imposes different requirements from a random access pattern on databases or files. Explicitly, we propose a new replica placement method, called  rotational mirrored declustering (RMD), to support high data availability for disk arrays in a VOD environment. In essence, RMD is similar to the conventional mirrored declustering in that replicas are stored in different disk arrays, however different from the latter in that the replica placements in different disk arrays under RMD are properly rotated. Combining the merits of prior chained and mirrored declustering methods, RMD is particularly ...
Efficient Parallel and Data Mining for Association Rules.
In this paper, we develop an algorithm, called PDM, to conduct parallel data mining for association rules. Consider a transaction as a collection of items, and a large itemset is a set of items such that the number of transactions containing it exceeds a pre-specified threshold. PDM is so designed that the global set of large itemsets can be identified efficiently and the amount of inter-node data exchange required is minimized. Specifically, with a given database partition, each processing node will collect (count) information on each itemset from its local database efficiently via a hashing method. The information discovered by each node is next shared with other nodes via some communication schemes. Then, PDM employs a technique, called clue-andpoll, to address the uncertainty due to the partial knowledge collected at each node by judiciously selecting a small fraction of the itemsets for the exchange of count information among nodes, thus reducing the communication cost. The global...
Efficient Parallel and Data Mining for Association Rules.
In this paper, we develop an algorithm, called PDM, to conduct parallel data mining for association rules. Consider a transaction as a collection of items, and a large itemset is a set of items such that the number of transactions containing it exceeds a pre-specified threshold. PDM is so designed that the global set of large itemsets can be identified efficiently and the amount of inter-node data exchange required is minimized. Specifically, with a given database partition, each processing node will collect (count) information on each itemset from its local database efficiently via a hashing method. The information discovered by each node is next shared with other nodes via some communication schemes. Then, PDM employs a technique, called clue-andpoll, to address the uncertainty due to the partial knowledge collected at each node by judiciously selecting a small fraction of the itemsets for the exchange of count information among nodes, thus reducing the communication cost. The global...
Performance Modeling For Designing Client%2FServer Systems.

Performance Modeling For Designing Client%2FServer Systems.

DASD Dancing A Disk Load Balancing Optimization Scheme for Video%2Don%2DDemand Computer.

An Effective Hash Based Algorithm for Mining Association Rules.
In this paper, we examine the issue of mining association rules among items in a large database of sales transactions. The mining of association rules can be mapped into the problem of discovering large itemsets where a large itemset is a group of items which appear in a sufficient number of transactions. The problem of discovering large itemsets can be solved by constructing a candidate set of itemsets first and then, identifying, within this candidate set, those itemsets that meet the large itemset requirement. Generally this is done iteratively for each large k-itemset in increasing order of k where a large k-itemset is a large itemset with k items. To determine large itemsets from a huge number of candidate large itemsets in early iterations is usually the dominating factor for the overall data mining performance. To address this issue, we propose an effective hash-based algorithm for the candidate set generation. Explicitly, the number of candidate 2-itemsets generated by the proposed algorithm is, in orders of magnitude, smaller than that by previous methods, thus resolving the performance bottleneck. Note that the generation of smaller candidate sets enables us to effectively trim the transaction database size at a much earlier stage of the iterations, thereby reducing the computational cost for later iterations significantly. Extensive simulation study is conducted to evaluate performance of the proposed algorithm. 1
A Performance Study of Workfile Disk Management for Concurrent Mergesorts in a Multiprocessor Database System.

Divergence Control for Distributed Database Systems.
This paper presents distributed divergence control algorithms for epsilon serializability for both homogeneous and heterogeneous distributed databases. Epsilon serializability allows for more concurrency by permitting non-serializable interleavings of database operations among epsilon transactions. We first present a strict 2-phase locking divergence control algorithm and an optimistic divergence control algorithm for a homogeneous distributed database system, where the local orderings of all the sub-transactions of a distributed epsilon transaction are the same. In such an environment, the total inconsistency of a distributed epsilon transaction is simply the sum of those of all its sub-transactions. We then describe a divergence control algorithm for a heterogeneous distributed database system, where the local orderings of all the sub-transactions of a distributed epsilon transaction may not be the same and the total inconsistency of a distributed epsilon transaction may be greater t...
Analytic Modeling and Comparisons of Striping Strategies for Replicated Disk Arrays.

Applying Segmented Right%2DDeep Trees to Pipelining Multiple Hash Joins.
The pipelined execution of multijoin queries in a multiprocessor-based database system is explored in this paper. Using hash-based joins, multiple joins can be pipelined so that the early results from a join, before the whole join is completed, are sent to the next join for processing. The execution of a query is usually denoted by a query execution tree. To improve the execu-tion of pipelined hash joins, an innovative approach on query execution tree selection is proposed to exploit segmented right-deep trees, which are bushy trees of right-deep subtrees. We first derive an analytical mode1 for the execution of a pipeline segment, and then, in light of the model, develop heuristic schemes to de-termine the query execution plan based on a segmented right-deep tree so that the query can be efficiently executed. As shown by our simulation, the proposed approach, without incurring additional overhead on plan execution, possesses more flexibility in query plan generation, and can lead to query plans of better performance than those achievable by the previous schemes using right-deep trees. 
A Hierarchical Approach to Parallel Multiquery Scheduling.

Storage and Retrieval Methods to Support Fully Interactive Playout in a Disk%2DArray%2DBased Video Server.
One of the most important challenges in a video--on--demand (VOD) system is to support interactive browsing functions such as &#034;fast forward&#034; and &#034;fast backward.&#034; Typically, these functions impose additional resource requirements on the VOD system in terms of storage space, retrieval throughput, network bandwidth, etc. Moreover, prevalent video compression techniques such as MPEG impose additional constraints on the process since they introduce inter-frame dependencies. In this paper, we devise methods to support variable rate browsing for MPEG-like video streams and minimize the additional resources required. Specifically, we consider the storage and retrieval for video data in a disk-array-based video server and address the issue of distributing the retrieval requests across the disks evenly. The overall approach proposed in this paper for interactive browsing is composed of (1) a storage method, (2) sampling and placement methods, and (3) a playout method, where the sampling and plac...
Design and Analysis of a Look%2DAhead Scheduling Scheme to Support Pause%2DResume for Video%2Don%2DDemand Applications.
In a video-on-demand (VOD) system, subscribers can choose both the movie they wish to view and the time they wish to view it. In such an environment there are invariably hot videos which are requested by many viewers. The requirement that each viewer be able to independently pause the video at any instant and later resume the viewing with little delay can cause difficulties in batching viewers for each showing. Under batching, a single video stream is shared by multiple concurrent viewers and a resume request has to wait for additional stream capacity to become available before actual resumption can occur. The conventional approach to support on-demand pause-resume provides one video access stream to disks for each video request. This can greatly increase the disk arm requirement of a VOD system. In this paper, we propose a more efficient mechanism to support the pause-resume feature using look-ahead scheduling with look-aside buffering. The idea is to use buffering to improve the numb...
Characterization of Database Access Pattern for Analytic Prediction of Buffer Hit Probability
Abstract. The analytic prediction of buffer hit probability, based on the charac-terization of database accesses from real reference traces, is extremely useful for workload management and system capacity planning. The knowledge can be help-ful for proper allocation of buffer space to various database relations, as well as for the management of buffer space for a mixed transaction and query environment. Access characterization can also be used to predict the buffer invalidation effect in a multi-node environment which, in turn, can influence transaction routing strate-gies. However, it is a challenge to characterize the database access pattern of a real workload reference trace in a simple manner that can easily be used to compute buffer hit probability. In this article, we use a characterization method that distin-guishes three types of access patterns from a trace: (1) locality within a transaction, (2) random accesses by transactions, and (3) sequential accesses by long queries. We then propose a concise way to characterize the access skew across randomly accessed pages by logically grouping the large number of data pages into a small number of partitions such that the frequency of accessing each page within a par-tition can be treated as equal. Based on this approach, we present a recursive binary partitioning algorithm that can infer the access skew characterization from the buffer hit probabilities for a subset of the buffer sizes. We validate the buffer hit predictions for single and multiple node systems using production database traces. We further show that the proposed approach can predict the buffer hit probability of a composite workload from those of its component files. Key Words. Database access characterization, access skew, sequential access, ref-erence trace, workload management, analytic prediction.
Support for Fully Interactive Playout in Disk%2DArray%2DBased Video Server.

Multiversion Divergence Control of Time Fuzziness.
Epsilon Serializability (ESR) has been proposed to manage and control inconsistency in extending the classic transaction processing that has been based on serializability. ESR increases transaction processing system concurrency by tolerating a bounded amount of inconsistency. In this paper, we present multiversion divergence control (mvDC) algorithms that support ESR with not only value but also time fuzziness in multiversion databases. Unlike value fuzziness, accumulating time fuzziness is semantically different. A simple summation of the length of two time intervals may either underestimate the total time fuzziness, resulting in incorrect execution, or overestimate the total time fuzziness, unnecessarily degrading the effectiveness of mvESR. In this paper, we present a new operation, called TimeUnion, to accurately accumulate the total time fuzziness. In addition, we describe two mvDC algorithms that can correctly bound the inconsistency in time and value for mvESR. Because of the ac...
Data Placement and Buffer Management for Concurrent Mergesorts with Parallel Prefetching.

On Parallel Transaction Processing in a Coupled System.
In this paper, we conduct a performance study on parallel transaction processing in a coupled system, where a coupled system is a multi-node system with a shared global buffer. We develop a multiplesystem simulator and obtain several performance results from it. This simulator has been run against three workloads, and the coupled system behavior with these three different inputs is studied. Several statistics, including those on local and global buffer hits, page writes to the global buffer, cross-invalidations and castouts, are comparatively analyzed, and their relationship to the degree of data skew is explored. 1 Introduction  Due mainly to the rapid technology advances, it has recently become very attractive to couple multiple systems for database transaction processing in order to address the increasing demand for better capacity, availability and cost-performance. Among others, one method to couple multiple systems is the data sharing approach [3] [6] [16], which is also referred...
Dynamic Parity Grouping for Improving Write Performance of RAID%2D5 Disk Arrays.

Scheduling Multiple Queries on a Parallel Machine.
There has been a good deal of progress made recently towards the efficient parallelization of individual phases of single queries in multiprocessor database systems. In this paper we devise and evaluate a number of scheduling algorithms designed to handle multiple parallel queries. One of these algorithms emerges as a clear winner. This algorithm is hierarchical in nature: In the first phase, a good quality precedence-based schedule is created for each individual query and each possible number of processors. This component employs dynamic programming. In the second phase, the results of the first phase are used to create an overall schedule of the full set of queries. This component is based on previously published work on nonprecedence-based malleable scheduling. Even though the problem we are considering is NP-hard in the strong sense, the multiple query schedules generated by our hierarchical algorithm are seen experimentally to achieve results which are close to optimal.  1 Introdu...
On Parallel Execution of Multiple Pipelined Hash Joins.
In this paper we study parallel execution of multiple pipelined hash joins. Specifically, we deal with two issues, processor allocation and the use of hash filters, to improve parallel execution of hash joins. We first present a scheme to transform a bushy execution tree to an allocation tree, where each node denotes a pipeline. Then, processors are allocated to the nodes in the allocation tree based on the concept of synchronous execution time such that inner relations (i.e., hash tables) in a pipeline can be made available approximately the same time. In addition, the approach of hash filtering is investigated to further improve the overall performance. Performance studies are conducted via simulation to demonstrate the importance of processor allocation and to evaluate various schemes using hash filters. Simulation results indicate that processor allocation based on the allocation tree significantly outperforms that based on the original bushy tree, and that the effect of hash filte...
Asymtotic Performance of a Buffer Model in a Data Sharing Environment.

On Parallel Execution of Multiple Pipelined Hash Joins.
In this paper we study parallel execution of multiple pipelined hash joins. Specifically, we deal with two issues, processor allocation and the use of hash filters, to improve parallel execution of hash joins. We first present a scheme to transform a bushy execution tree to an allocation tree, where each node denotes a pipeline. Then, processors are allocated to the nodes in the allocation tree based on the concept of synchronous execution time such that inner relations (i.e., hash tables) in a pipeline can be made available approximately the same time. In addition, the approach of hash filtering is investigated to further improve the overall performance. Performance studies are conducted via simulation to demonstrate the importance of processor allocation and to evaluate various schemes using hash filters. Simulation results indicate that processor allocation based on the allocation tree significantly outperforms that based on the original bushy tree, and that the effect of hash filte...
Scheduling Parallel Tasks to Minimize Average Response Time.
:  Interval orders are partial orders defined by having interval representations. It is well known that a transitively oriented digraph G is an interval order iff its (undirected) complement is chordal. We investigate parallel algorithms for the following scheduling problem: Given a system consisting of a set T of n tasks (each requiring unit execution time) and an interval order ! over T , and given m identical parallel processors, construct an optimal (i.e., minimal length) schedule for (T; !).  Our algorithm is based on a subroutine for computing so-called scheduling distances, i.e., the minimal number of time steps needed to schedule all those tasks succeeding some given task  t and preceding some other task t  0  . For a given interval order with n tasks, these scheduling distances can be computed using n  3  processors and O(log  2  n) time on a CREW-PRAM. We then give an incremental version of the scheduling distance algorithm, which can be used to compute the empty slots in an ...
Scheduling Parallelizable Tasks to Minimize Average Response Time.

On Index Selection Schemes for Nested Object Hierarchies.
In this paper we address the problem of devising a set of indexes for a nested object hierarchy in an object-oriented database to improve the overall system performance. It is noted that the effects of two indexes could be entangled in that the inclusion of one index might affect the benefit achievable by the other index. Such a phenomenon is termed index interaction. Clearly, the effect of index interaction needs to be taken into consideration when a set of indexes is being built. The index selection problem is first formulated and four index selection algorithms are evaluated via simulation. The effects of different objective functions, which guide the search in the index selection algorithms, are also investigated. It is shown by simulation results that the greedy algorithm which is devised in light of the phenomenon of index interaction performs fairly well in most cases. Sensitivity analysis for various database parameters is conducted. Index Term: Object-oriented databases, indexing, nested object hierarchy, index interaction.
Performance Modelling and Comparisons of Global Shared Buffer Management Policies in a Cluster Environment.

A Graph Theoretical Approach to Determine a Join Reducer Sequence in Distributed Query Processing.

Buffer Analysis for a Data Sharing Environment with Skewed Data Access.

Performance Analysis of Affinity Clustering on Transaction Processing Coupling Architecture.

New Algorithms for Parallelizing Relational Database Joins in the Presence of Data Skew.

Optimal NODUP All%2Dto%2DAll Broadcast Schemes in Distributed Computing Systems.

A Performance Study of Robust Distributed Load Sharing Strategies.

Performance Evaluation of Transaction Processing Coupling Architectures for Handling System Dynamics.

An Analytical Model of Reconstruction Time in Mirrored Disks.

Optimization of the Grouped Sweeping Scheduling %28GSS%29 with Heterogeneous Multimedia Streams.

Parallel Query Processing.
With relations growing larger and queries becoming more complex, parallel query processing is an increasingly attractive option for improving the performance of database systems. The objective of this paper is to examine the various issues encountered in parallel query processing and the techniques available for addressing these issues. The focus of the paper is on the join operation with both sort-merge join and hash joins being considered. Three types of parallelism can be exploited, namely intra-operator, inter-operator, and inter-query parallelism. In intra-operator parallelism the major issue is task creation, and the objective is to split a join operation into tasks in a manner such that the load can be spread evenly across a given number of processors. This is a challenge when the values on the join attribute are not uniformly distributed. Inter-operator parallelism can be achieved either through parallel execution of independent operations or through pipelining. In either case,...
Decentralized Consensus Protocols with Multi%2DPort Communication.
We develop in this paper efficient decentralized consensus protocols for a distributed system with multiport communication. Given an arbitrary number of nodes in a system, the proposed protocols can reach the consensus in the minimal numbers of message steps. Specifically, we develop two classes of decentralized consensus protocols: the one without an initiator  and the one with an initiator. We first present the case of 1-port communication, i.e., each node can send out one message in one step, and show algorithms G 1 and G 2 . We then develop our results for the case of multi-port communication, say k-port communication, meaning that each node can send out k messages in one step, and derive algorithms G 3 and G 4 . G 3 and G 4 are the general versions of G 1 and G 2 . The four algorithms presented in this paper are optimal in the sense that they complete the protocols in the minimal number of message steps required. The number of messages incurred by each algorithm is also derived. 1...
Distributed Divergence Control for Epsilon Serializability.

Database Access Characterization for Buffer Hit Prediction.

Dynamic Finite Versioning An Effective Versioning Approach to Concurrent Transaction and Query Processing.
Severe data contention may exist between short update transactions and long read-only queries if both are to access the same database through a conventional concurrency control method. In this paper, we present dynamic finite versioning (DFV) schemes to effectively support concurrent processing of transactions and queries. Without acquiring locks, queries read from a small, fixed number of dynamically derived, transaction-consistent, but maybe slightly obsolete,  logical snapshots of the database. On the other hand, transactions access the most up-to-date data in the database without data contention from queries. Intermediate versions created between snapshots are automatically discarded. Furthermore, dirty pages updated by active transactions are allowed to be written back into the database before commitment (i.e., the STEAL policy), and at the same time, consistent logical snapshots can be advanced automatically without quiescing the ongoing transactions or queries. 1 Introduction  C...
Performance Analysis of a Dual Striping Strategy for Replicated Disk Arrays.

Issues in the Design of Multi%2DServer File Systems to Cope with Load Skew.

Modeling and Analysis of Transaction Processing Systems.
Standard locking (two-phase locking with on-demand lock requests and blocking upon lock conflict) is the primary concurrency control (CC) method for centralized databases. The main source of performance degradation with standard locking is blocking, whereas transaction (txn) restarts to resolve deadlocks have a secondary effect on performance. We provide a performance analysis of standard locking that accurately estimates its performance degradation leading to thrashing. We next introduce two sets of methods to cope with its performance limitations. Restartoriented locking methods selectively abort txns to increase the level of concurrency for active txns with respect to standard locking in high-contention environments. For example, the running-priority method aborts blocked txns based on the essential blocking principle, which only allows blocking by active txns. The waitdepth-limited (WDL) method further minimizes wasted processing by basing abort decisions on the progress made by a txn. Restart waiting serves as a load-control mechanism by deferring the restart of an aborted txn until conflicting txns have left the system. These two methods have performance superior to other restartoriented
Performance Comparison of Thrashing Control Policies for Concurrent Mergesorts with Parallel Prefetching.

On Optimal Processor Allocation to Support Pipelined Hash Joins.
In this paper, we develop algorithms to achieve optimal processor allocation for pipelined hash joins in a multiprocessorbased database system. A pipeline of hash joins is composed of several stages, each of which is associated with one join operation. The whole pipeline is executed in two phases: (1) the table-building phase, and (2) the tuple-probing phase. We focus on the problem of allocating processors to the stages of a pipeline to minimize the query execution time. We formulate the processor allocation problem as a twophase mini-max optimization problem, and develop three optimal allocation schemes under three different constraints. The effectiveness of our problem formulation and solution is verified through a detailed tuple-by-tuple simulation of pipelined hash joins. Our solution scheme is general and applicable to any optimal resource allocation problem formulated as a two-phase mini-max problem. 1 Introduction  In recent years, multiprocessor-based parallel database machine...
Applying Hash Filters to Improving the Execution of Bushy Trees.
In this paper, we explore an approach of interleaving a bushy execution tree with hash filters to improve the execution of multi-join queries. The effect of hash filters is evaluated first. Then, an efficient scheme to determine an effective sequence of hash filters for a bushy execution tree is developed, where hash filters are built and applied based on the join sequence specified in the bushy tree so that not only is the reduction effect optimized but also the cost associated is minimized. Various schemes using hash filters are implemented and evaluated via simulation. It is experimentally shown that the application of hash filters is in general a very powerful means to improve the execution of multi-join queries, and the improvement becomes more prominent as the number of relations in a query increases. 1 Introduction  In relational database systems, joins are the most expensive operations to execute. Applications involving decision support and complex objects usually have to speci...
Performance comparison of dynamic policies for remote caching.

Combining Join and Semi%2DJoin Operations for Distributed Query Processing.

A Parallel Sort Merge Join Algorithm for Managing Data Skew.

Replication Algorithms in a Remote Caching Architecture.

A Parallel Hash Join Algorithm for Managing Data Skew.

Performance Analysis of Buffer Coherency Policies in a Multisystem Data Sharing Environment.

Performance Analysis of Concurrency Control Using Locking with Deferred Blocking.

On the Analytical Modeling of Database Concurrency Control.

Grouped Sweeping Scheduling for DASD%2Dbased Multimedia Storage Management.

Buffer Management Based on Return on Consumption in a Multi%2DQuery Environment

Design and Modeling of Clustered RAID.

Performance Comparison of Active%2DSender and Active%2DReceiver Policies for Distributed Caching.

Efficient Decentralized Consensus Protocols in a Distributed Computing System.

A Comparison of Regression%2DBased Load Sharing Strategies for Distributed Database Environments.

Effect of System Dynamics on Coupling Architectures for Transaction Processing.

Divergence Control for Epsilon%2DSerializability.

Distributed Object Replication Strategies for a Remote Caching Architecture.

Scheduling and Processor Allocation for Parallel Execution of Multi%2DJoin Queries.

Distributed Object Replication Strategies for a Remote Caching Architecture.

Mon%2DSong Chen
Future advances in networking and storage will enable a wide spectrum of computer mediated structured collaborations among individuals. In this paper, we present a model that can capture diverse types of structured collaborations. The model combines both efficiency and power via a hierarchy of three abstractions, at the lowest level of which are streams for media communication modulated by access rights of participants within collaborations. The higher two levels of abstractions are sessions, which represent collections of semantically related media streams, and conferences, which represent temporally related sequences of sessions. Using these abstractions, the model supports unification of both synchronous and asynchronous collaborations, sophisticated access control, and intra-group and inter-group collaborations, yielding a powerful set of building blocks for constructing multimedia applications and a rich environment for carrying out structured multimedia collaborations.  KEYWORDS ...
Performance Analysis of Dynamic Finite Versioning for Concurrency Transaction and Query Processing.
In this paper, we analyze the performance of dynamic finite versioning (DFV) schemes for concurrent transaction and query processing, where a finite number of consistent snapshots can be derived for query access. We develop analytical models based on a renewal process approximation to evaluate the performance of DFV using M  2 snapshots. The storage overhead and obsolescence faced by queries are measured. Simulation is used to validate the analytical models and to evaluate the trade-offs between various strategies for advancing snapshots when M ? 2. The results show that (1) the analytical models match closely with simulation; (2) both the storage overhead and obsolescence are sensitive to the snapshot-advancing strategies, especially for M ? 2 snapshots; and (3) generally speaking, increasing the number of snapshots demonstrates a trade-off between storage overhead and query obsolescence. For cases with skewed access or low update rates, a moderate increase in the number of snapshots ...
Scheduling Parallelizable Tasks Putting it All on the Shelf.

Characterization of Database Access Skew in a Transaction Processing Environment.

Performance Analysis of Coherency Control Policies through Lock Retention.

Approximate Algorithms Scheduling Parallelizable Tasks.

Impact of Workload Partitionability on the Performance of Coupling Architectures for Transaction Processing.

Using Segmented Right%2DDeep Trees for the Execution of Pipelined Hash Joins.
In this paper, we explore the execution of pipelined hash joins in a multiprocessor-based database system. To improve the query execution, an innovative ap-proach on query execution tree selection is proposed to exploit segmented right-deep trees, which are bushy trees of right-deep subtrees. We first derive an analyt-ical model for the execution of a pipeline segment, and then, in light of the model, develop heuristic schemes to determine the query execution plan based on a seg-mented right-deep tree so that the query can be ef-ficiently executed. As shown by our simulation, the proposed approach, without incurring additional over-head on plan execution, possesses more flexibility in query plan generation, and leads to query plans of sig-nificantly better performance than those achievable by the previous schemes using right-deep trees. 1
Interleaving a Join Sequence with Semijoins in Distributed Query Processing.
In distributed query processing, the conventional approach to reduce the amount of data transmission is to first apply a sequence of semijoins as &#034;reducers&#034; and then ship the resultant relations to the final site to carry out the join operations. Recently, it has been shown that the approach of applying a combination of joins and semijoins as reducers can lead to substantially larger reduction on data transmission required. In this paper, we develop an efficient heuristic approach to determine an effective sequence of semijoin and join reducers. Semijoins whose execution will reduce the amount of data transmission required to perform a join sequence are termed beneficial semijoins for that join sequence. Note that beneficial semijoins include the conventional profitable semijoins and the gainful semijoins that are not profitable themselves but become beneficial due to the inclusion of join reducers. This type of dependency between semijoin and join reducers complicates the identificati...
Analysis of Concurrency%2DCoherency Control Protocols for Distributed Transaction Processing Systems with Regional Locality.

Analysis of Hybrid Concurrency Control Schemes For a High Data Contention Environment.

On Workload Characterization of Relational Database Environments.
As relational database systems become increasingly popular, there is a clear need to better understand the workload so systems can be designed or tuned more effectively. A RElational Database Workload AnalyzeR (REDWAR) is developed to characterize the workload in a DB2 environment. This is applied to study a production DB2 system where an SQL trace for a two hour interval and an image copy of the database catalog were obtained. The results of the workload study are summarized. Here we focus on the structure and complexity of SQL statements, the makeup and run-time behavior of transactions/queries, and the composition of relations and views. The results obtained provide the important information needed to build a benchmark workload to evaluate alternative design trade-offs of database systems.  Index Terms: relational databases, workload characterization, DB2.  1 Introduction  As relational database systems grow increasingly popular, throughput and response time requirements are becomin...
Performance comparisons of buffer coherency policies.

An Effective Algorithm for Parallelizing Hash Joins in the Presence of Data Skew.

Determining Beneficial Semijoins for a Join Sequence in Distributed Query Processing.

Optimal Buffer Allocation in A Multi%2DQuery Environment.

Dynamic Load Sharing in the Presence of Information Obsolescence in Distributed Database Environments.

Policies for Efficient Resource Utilization in a Remote Caching Architecture.

Optimal All%2Dto%2DAll Broadcasting Schemes in Distributed Systems.

Comparative Performance of Parallel Join Algorithms.


Analytical Modeling of a Hierarchical Buffer for a Data Sharing Environment.


Modeling and Analysis of a Time%2DStamp History Based Certification Protocol for Concurrency Control.

An Adaptive Strategy for Load Sharing in Distributed Database Environment with Information Lags.

An Effective Algorithm for Parallelizing Sort Merge in the Presence of Data Skew.

Using Join Operations as Reducers in Distributed Query Processing.

Using Combination of Join and Semijoin Operations for Distributed Query Processing.

Concurrency Control Using Locking with Deferred Blocking.

Database Buffer Model for the Data Sharing Environment.

On Workload Characterization of Relational Database Environments.
As relational database systems become increasingly popular, there is a clear need to better understand the workload so systems can be designed or tuned more effectively. A RElational Database Workload AnalyzeR (REDWAR) is developed to characterize the workload in a DB2 environment. This is applied to study a production DB2 system where an SQL trace for a two hour interval and an image copy of the database catalog were obtained. The results of the workload study are summarized. Here we focus on the structure and complexity of SQL statements, the makeup and run-time behavior of transactions/queries, and the composition of relations and views. The results obtained provide the important information needed to build a benchmark workload to evaluate alternative design trade-offs of database systems.  Index Terms: relational databases, workload characterization, DB2.  1 Introduction  As relational database systems grow increasingly popular, throughput and response time requirements are becomin...
The Effect of Skewed Data Access on Buffer Hits and Data Contention an a Data Sharing Environment.

Effectiveness of parallel processing in database systems.

Integrated approach to buffer management and query optimization.

Analysis of Replication in Distributed Database Systems.

Effectiveness of Parallel Joins.
Join is an expensive and frequently used operation whose parallelization is highly desirable. However effectiveness of parallel joins depends on the ability to evenly divide load among processors. Data skew can have a disastrous effect on performance. Although many skew-handling algorithms have been proposed they remain generally inefficient in the case of multi-joins due to join product skew, costly and unnecessary redistribution and communication costs. A parallel join algorithm called fa join has been introduced in an earlier paper with deterministic and near-perfect balancing properties. Despite its advantages, fa join is sensitive to the correlation of the attribute value distributions in both relations. We present here an improved version of the algorithm called Sfa join with a symmetric treatment of both relations. Its predictably low join-product and attribute-value skew makes it suitable for repeated use in multi-join operations. Its performance is analyzed theoretically and expe...
An Effective Approach to Vertical Partitioning for Physical Design of Relational Databases.



Adaptive Transaction Routing in a Heterogeneous Database Environment.

Limiting Factors of Join Performance on Parallel Processors.

Analysis of Parallel Processing Architectures for Database Systems.

Performance Analysis of Optimistic Concurrency Control Schemes for Systems with Large Memory.

Performance Comparision of Concurrency Control Protocols for Transaction Processing Systems with Regional Locality.

Integration of Buffer Management and Query Optimization in Relational Database Environment.

Robust Transaction%2DRouting Strategies in Distributed Database Systems.

Integrated Concurrency%2DCoherency Controls for Multisystem Data Sharing.

Multisystem Coupling by a Combination of Data Sharing and Data Partitioning.

Multisystem Coupling by a Combination of Data Sharing and Data Partitioning.

On Optimal Site Assignment for Relations in the Distributed Database Environment.

Performance Comparison of IO Shipping and Database Call Shipping Schemes in Multisystem Partitioned Databases.

Effect of Skew on Join Performance in Parallel Architectures.

Robust Transaction Routing in Distributed Database Systems.

Load Sharing in Hybrid Distributed %2D Centralized Database Systems.

Site Assignment for Relations and Join Operations in the Distributed Transaction Processing Environment.

A Hybrid Data Sharing %2D Data Partitioning Architecture for Transaction Processing.

Performability comparison of configurable duplex systems.

Tradeoffs Between Coupling Small and Large Processors for Transaction Processing.

Optimal Design and Sequential Analysis of VLSI Testing Strategy.



An Adaptive Optimization Model with Applications to Testing.

VLSI Circuit Testing Using an Adaptive Optimization Model.

Relation Assignment in Distributed Transaction Processing Environment.

On Centralized versus Geographically Distributed Database Systems.

A Vertical Partitioning Algorithm for Relational Databases.

Design and Analysis of Integrated Concurrency%2DCoherence Controls.

Analysis of Fault Tolerant Multiprocessor Architectures for Lock Engine Design.

Progressive Transaction Recovery in Distributed DB%2FDC Systems.

Analysis of Affinity Based Routing in Multi%2DSystem Data Sharing.

Dynamic Load Sharing in Distributed Database Systems.

Performability Analysis of Operation Modes of Configurable Duplex Systems.

On Coupling Partitioned Database Systems.

Analysis of Multi%2DSystem Function Request Shipping.

Analysis of Recovery Protocols in Distributed On%2DLine Transaction Processing Systems.

On Coupling Many Small Systems for Transaction Processing.

On Coupling Many Small Systems for Transaction Processing.

Transaction Recovery in Distributed DB%2FDC Systems A Progressive Approach.

On Affinity Based Routing in Multi%2DSystem Data Sharing.

On Multisystem Coupling Through Function Request Shipping.

Distributed Concurrency Control Analysis for Data Sharing.

Modelling of Centralized Concurrency Control in a Multi%2DSystem Environment.

